1 CHAMADA - LINGUAGENS FORMAIS E AUTÔMATOS

Prévia do material em texto

Questão 1 
A hierarquia de Chomsky é uma classificação das linguagens formais. Esta classificação possui 
quatro níveis, são eles: Linguagens regulares, Linguagens livres de contexto, linguagem 
sensíveis ao contexto e Linguagens irrestritas. Analise as regras de produções abaixo e 
associe com a sua gramá ca correta. 
I- P: A→α onde A pertence V e α uma palavra de (V U T )*. 
II- P: A→αB (A→Bα) ou A→α tal que A, B pertence V e α pertence ∑*. 
III- α→β com α, β pertencentes (V U T )* e |α| ≤ |¿| . 
1- Gramá ca Regular; 
2- Gramá ca Livre de Contexto; 
3- Gramá ca Sensível ao contexto; 
Assinale a alterna va que contém a sequência correta da associação: 
A)I- 1; II-3; III-2; 
B)I- 2; II- 1; III- 3; 
C)I-1; II-2; III-3; 
D)I-3; II-2; III- 1; 
E)I-2; II- 3; III- 1; 
Questão 2 
A hierarquia de Chomsky é uma classificação das linguagens formais. Esta classificação possui 
quatro níveis, são eles: Linguagens regulares, Linguagens livres de contexto, linguagem 
sensíveis ao contexto e Linguagens irrestritas. Sobre a hierarquia de Chomsky, analise as 
afirma vas a seguir e marque V para verdadeira e F para falso: 
 
( ) - As linguagens regulares, também conhecidas como do po 3, possui o po de gramá ca 
mais simples. São os autômatos com pilha que são os seus reconhecedores; 
( ) - As linguagens livres de contexto, também são conhecidas como po 2, esse po de 
linguagem possui um formalismo maior que a linguagem de po 3; 
( )- As linguagens irrestritas ( po 0), não possuem restrição, a única especificação é ter pelo 
menos uma variável do lado esquerdo das produções da grama ca. Não existe reconhecedor 
para este po de linguagem; 
Agora, assinale a alterna va que apresenta a sequência CORRETA: 
A)V-V-V; 
B)V-V-F; 
C)V-F-V; 
D)F-V-V; 
E)F-F-F; 
Questão 3 
_________________ é uma forma compacta de descrever linguagens regulares. Trata-se de 
uma definição que faz uso do fato de que a concatenação, união e _____________ de 
linguagens regulares são regulares. 
Assinale a alterna va que complete a frase corretamente: 
A)Expressão regular; caractere; 
B)Expressão regular; fecho de Kleene. 
C)Autômato finito determinís co; estados; 
D)Autômato finito não determinís co; estados; 
E)Autômato finito determinís co; transições; 
Questão 4 
As funções recursivas de Kleene são funções recursivas parciais construídas com base em 
funções básicas, u lizando três pos de construções. 
Assinale a alterna va que apresente esses três pos de construções: 
A)Composição; recursão; minimização; 
B) Divisão; minimização; adição; 
C)Composição; minimização; adição; 
D)Operacional; axiomá co; denotacional; 
E)Composição; recursão; adição; 
Questão 5 
A concatenação é um conceito sobre a linguagem que podemos afirmar que pode ser 
realizada entre quaisquer palavras que compõem a linguagem. Sobre este conceito, analise 
as sentenças a seguir e marque V para verdadeira e F para falso: 
( ) Quando concatenamos uma cadeia α com o comprimento | α |= 3 e uma cadeia β com um 
comprimento | β |=4 , o resultado final desta concatenação será uma cadeia α β com o 
comprimento igual |α β| =7; 
( ) Quando concatenamos a palavra vazia (ε) a outra palavra, o comprimento desta palavra 
deve ser adicionada mais uma unidade; 
( ) Quando concatenamos as palavras, a ordem de concatenação não é importante, 
implicando sempre no mesmo resultado, por exemplo, a concatenação de αβ= βα; 
Agora, assinale a alterna va que apresenta a sequência CORRETA: 
A)V-F-V; 
B)V-F-F; 
C)F-V-V; 
D)V-V-V; 
E)F-F-F; 
Questão 6 
Sendo a gramá ca G composta por: variáveis, terminais, produções e símbolo inicial. Analise 
a gramá ca a seguir: 
G1 = ({S}, {a,b}, P1, S); onde : 
P1= { S→ aaSb | aab } 
A par r da gramá ca anterior, analise as alterna vas e assinale qual é a linguagem que é 
gerada pela gramá ca G1: 
A)L = {ab}; 
B)L={anbn | n ≥ 1} 
C)L={anbm | n ≤ m} 
D)L={a2nbn | n ≥ 1} 
E)L={anb2n | n ≥ 1} 
Questão 7 
Expressão regular é uma forma compacta de descrever as linguagens regulares. Logo, pode-
se extrair expressões regulares de autômatos finitos. Sabendo disso, analise o seguinte 
autômato finito: 
 
Anexo - Consulte a imagem em melhor resolução no final do cadernos de questões. 
Assinale a alterna va correta que contenha a expressão regular que represente o autômato 
finito anterior: 
A)a(b)* + (b)*a(b)* 
B)aab(b)*+bba(b)* 
C)aa(b)*+(b)*a(b)* 
D)a(a)*b(b)*+b(b)*a(b)* 
E)(a)*b(b)*+(b)*a(b)* 
Questão 8 
Observe a imagem do autômato a seguir: 
 
Anexo - Consulte a imagem em melhor resolução no final do cadernos de questões. 
 
 
Agora, analise as afirma vas a seguir sobre o autômato da imagem: 
I- O autômato é do po finito determinís co; 
II- A palavra 00 e 0000 são aceitas pelo autômato; 
III- As palavras aceitas por este autômato são aquelas que necessariamente possuem 00 em 
sua composição; 
Agora, assinale a alterna va que apresenta a resposta CORRETA: 
A)Apenas a alterna va I está correta; 
B)As alterna vas I, II e III estão corretas. 
C)Apenas as alterna vas II e III estão corretas; 
D)Apenas as alterna vas I e II estão corretas; 
E)Apenas a alterna va II está correta; 
Questão 9 
 Linguagens regulares são categorizadas pela a hierarquia de Chomsky como do po 3, sendo 
esse po de linguagem as que contém a gramá ca mais simples. Sabendo das regras que 
compõem as produções das gramá cas. Assinale a alterna va que NÃO apresenta uma 
gramá ca regular: 
A)S → aA | b | c 
 A → bA |a 
 B → b 
B)S→ A | λ 
 A → Aa | a | c 
 B → Bb | S | b 
C)S → Aa | λ 
 A → Aa | a 
 B → Bb |b| c 
D)S → aAa | c 
 A → aA | a 
 B → bB | b 
E)S→ aA | x 
 A → B | a 
 B → bB | b 
Questão 10 
Expressão regular é uma forma compacta de descrever as linguagens regulares. Logo, pode-
se extrair expressões regulares de autômatos finitos. Sabendo disso, analise o seguinte 
autômato finito: 
 
A 
Anexo - Consulte a imagem em melhor resolução no final do cadernos de questões.ssinale a 
alterna va correta que contenha a expressão regular que represente o autômato finito 
anterior: 
 
 
 
 
A)cc*b*+ab*c* 
B)cc*b*ab*c 
C)ab*c*c*cc*bb* 
D)cc*b +ab*c 
E)cac*b*bcb*c* 
Questão 11 
A hierarquia de Chomsky é conhecida por classificar as linguagens formais. Essa classificação 
é também u lizada para relacionar as máquinas que são correspondentes a cada linguagem. 
Sabendo disso, analise as afirma vas a seguir: 
I- As máquinas correspondentes as linguagens regulares não u lizam pilhas, isso é devido 
pela simplicidade da gramá ca. Sua principal caracterís ca é o tempo de reconhecimento de 
uma palavra que é proporcional ao comprimento desta entrada; 
II- As máquina que correspondem a linguagem livres de contexto u lizam como 
reconhecedores os autômatos com pilha não determinís co. O seu tempo de 
reconhecimento é o dobro do tamanho da entrada; 
III- As linguagens recursivas são reconhecidas pelas máquina Universais, sendo este po de 
máquina também u lizado para o reconhecimento das linguagens enumeráveis 
recursivamente; 
Agora, assinale a alterna va que apresenta a resposta CORRETA: 
A)Apenas as alterna vas I e III estão corretas; 
B)Apenas as alterna vas I e II estão corretas; 
C)Apenas a alterna va I está correta; 
D)As alterna vas I, II e III estão corretas. 
E) Apenas a alterna va II está correta; 
Questão 12 
A hierarquia de Chomsky é uma classificação das linguagens formais. Esta classificação possui 
quatro níveis. Sobre a hierarquia de Chomsky, analise as afirma vas a seguir: 
 
I- As linguagens regulares, também conhecidas como do po 3, possui o po de gramá ca 
mais simples. Os autômatos finitos são u lizados como reconhecedores desta linguagem ; 
II- As linguagens livres de contexto, também são conhecidas como po 2, tem como 
reconhecedores os autômatos finitos não determinís cos. 
III- As linguagens irrestritas também são conhecidas como po 0, esse po de linguagem 
possui um formalismo maior que a linguagem 3. 
Agora, assinale a alterna va que apresentaa resposta CORRETA: 
A)Apenas a alterna va II está correta; 
B)As alterna vas I, II e III estão corretas. 
C)Apenas a alterna va I está correta; 
D)Apenas as alterna vas I e II estão corretas; 
E)Apenas as alterna vas I e III estão corretas;