Simulado Automatos

Prévia do material em texto

1- As operações sobre as Linguagens Livres do Contexto (LLC), tem-se que: 
a) é fechada para as operações de união e concatenação, e não é fechada para as operações de intersecção e complemento. 	Comment by Gabriel Gomes: Alternativa correta: (A) Porque não pode dizer com certeza que vai produzir na intersecção e no complemento uma linguagem com as mesmas características de união e concatenação
b) é fechada para as operações de intersecção e complemento, e não é fechada para as operações de união e concatenação. 
c) é fechada para as operações de união, concatenação, intersecção e complemento. d) é fechada para as operações de concatenação e intersecção, e não é fechada para as operações união e complemento. 
e) não é fechada para as operações de união, intersecção, concatenação e complemento. 
2 - Das afirmações abaixo: 
I – O Algoritmo de Early é considerado o mais rápido algoritmo de reconhecimento conhecido para Gramáticas Livres do Contexto; é do tipo top-down que parte do símbolo inicial e executa sempre a derivação mais à esquerda. Cada ciclo gera um terminal, o qual é comparado com o símbolo de entrada. A comparação com sucesso determina a construção de um conjunto de produções que, potencialmente, pode gerar o próximo símbolo. 
II – O Algoritmo de Cocke-Younger-Kasami é construído sobre uma gramática na Forma Normal de Chomsky; gera bottom-up todas as árvores de derivação da entrada em um tempo de processamento proporcional a | w |³. A ideia básica do algoritmo é a construção de uma tabela triangular de derivação, sendo que cada célula representa o conjunto de raízes que pode gerar a correspondente sub-árvore.
III – Sobre os algoritmos de reconhecimento, nas LLC, os reconhecedores podem ser, basicamente, de dois tipos: Top-Down ou Preditivo e Bottom-Up. 
IV – Top-Down ou Preditivo. Constrói uma árvore de derivação para a palavra de entrada (a ser reconhecida) a partir das folhas em direção à raiz.	Comment by Gabriel Gomes: 	Comment by Gabriel Gomes: Correto; afirma a definição do algoritmo.	Comment by Gabriel Gomes: O algoritmo é construído em cima da FNC. Faz varredura Bottom-Up, tem o mesmo tempo de processamento que de Early. Ideia de construção também está correta.	Comment by Gabriel Gomes: Correto. Apenas!	Comment by Gabriel Gomes: Está incorreto pois Top-Down começa a partir da raiz e vai derivando em direção as folhas.
Pode-se dizer que: 
a) Todas as informações acima são incorretas 
b) I, II e III são corretas 	Comment by Gabriel Gomes: Logo, tendo I, II e III como corretas a alternativa correspondente é B
c) Todas as informações acima são corretas 
d) II, III e IV são corretas 
e) II e IV são corretas 
3 - O estudo das Linguagens livres do contexto é importante pois: 
I - Compreende um universo mais amplo de linguagens (comparativamente com as regulares); 	Comment by Gabriel Gomes: Correto
II - Os algoritmos reconhecedores e geradores que implementam as Linguagens Livres do Contexto são relativamente simples e possuem uma boa eficiência; 	Comment by Gabriel Gomes: Subjetivo para correto, pois não foi especificado o algoritmo utilizado. No geral pode-se considerar uma boa eficiência.
III - É desenvolvido a partir de uma gramática livre do contexto (GLC), onde as regras de produção são definidas de forma mais livre que na gramática regular; 	Comment by Gabriel Gomes: Correto
IV – É desenvolvido, também, através do autômato com pilha, cuja estrutura básica é análoga à do autômato finito, adicionado a ele uma memória auxiliar tipo pilha (a qual pode ser lida ou gravada). 	Comment by Gabriel Gomes: Subjetivo para incorreto
Dos itens acima pode-se dizer que: 
a) todos os itens são corretos 
b) todos são incorretos 
c) são corretos apenas os itens I e III 	Comment by Gabriel Gomes: Logo, analisando as afirmações mais corretas a resposta é C) I e III
d) são corretos apenas os itens II e III 
e) são corretos apenas os itens I e IV 
4 - Um analisador léxico usado em compiladores é um exemplo de aplicação de MMo (Máquina de Moore). Um analisador léxico é um autômato finito, em geral determinístico, que identifica os componentes básicos de uma linguagem de programação, como, por exemplo, palavras reservadas, números, identificadores, separadores etc. Para isso, a MMo teria: 
a) Um estado final, associado a cada unidade léxica; cada estado final possui uma saída, que descreve a unidade identificada; para os demais estados (não finais) a saída gerada é a cadeia vazia. 	Comment by Gabriel Gomes: Correto (exemplo com a palavra f o r) onde a palavra só é gerada se chegar ao estado final
b) Um estado final, associado a cada unidade léxica; cada estado final não possui uma saída, que descreve a unidade identificada; para os demais estados (não finais) a saída gerada é a cadeia vazia. 
c) Apenas a cadeia vazia. 
d) Um estado inicial, associado a cada unidade léxica; cada estado final não possui uma saída, que descreve a unidade identificada; para os demais estados (não finais) a saída gerada é a cadeia vazia. 
e) A saída gerada, a cadeia não vazia. (A resposta está incompleta)
5-Seja a linguagem L = { w | w ∈ {a, b}* e w começa com b e termina com a}, a função programa δ do AFD M = ({S, A, B}, {a, b}, δ, S, {B}) que processa L é: 
a) δ (S, b) = A; δ (A, b) = A; δ (A, a) = B; δ (B, a) = B; δ (B, b) = A 	Comment by Gabriel Gomes: Após montar o autômato, é a única alternativa que satisfaz a Linguagem.
b) δ (A, b) = A; δ (A, a) = B; δ (B, a) = B; δ (B, b) = A 
c) δ (S, b) = A; δ (A, b) = A; δ (B, a) = B; δ (B, b) = b 
d) δ (S, b) = A; δ (A, b) = A; δ (B, b) = A 
e) δ (S, b) = A; δ (A, b) = B; δ (A, a) = a; δ (B, a) = B; δ (B, b) = A 
6-Seja a linguagem L = { w | w ∈ {a, b}* e w começa com b e termina com a}, a produção da gramática G = ({S, A, B}, {a, b}, S, P) que gera L é dada por: 
a) P = {S -> bA, A -> bA | aB, B -> aB | bA | λ} 	Comment by Gabriel Gomes: Única alternativa que corresponde a produção à construção do autômato. 
b) P = {S -> bA, B -> aB | bA | λ} 	Comment by Gabriel Gomes: Falta o Estado A com seus terminais e estados destino.
c) P = {S -> bA, A -> aB, B -> aB | bA | λ} 
d) P = {S -> b, A -> A | B, B -> aB | bA | λ} 
e) P = {S -> bA, A -> bA | aB, B -> λ} 
7-Dada as afirmações abaixo: 
I – Em relação às linguagens regulares tem-se vários caminhos para descrevê-las: AFD, AFN, ER e gramáticas regulares 	Comment by Gabriel Gomes: Para descrever uma linguagem regular utiliza-se os caminhos citados.
II – A classe das linguagens regulares é fechada para as seguintes operações: união, intersecção, concatenação e complemento 	Comment by Gabriel Gomes: É fechada para todas as operações citadas.
III – Para mostrar que uma linguagem é regular é suficiente representá-la usando um dos formalismos apresentados (AF, ER, GR), já a prova de que ela não é regular necessita análise caso a caso. Uma forma é usar o lema do Bombeamento. 	Comment by Gabriel Gomes: Correto. Para representar que a linguagem é regular usa-se estes 3. Para representar que não é regular precisa-se analisar (EX LLC pode ou não ser regular, não necessariamente irregular). Uma das maneiras é utilizar este lema/teorema;
IV – Se M1 e M2 são autômatos finitos, então existe um algoritmo para determinar se L(M1) = L(M2)	Comment by Gabriel Gomes: Correto. Reconhece as duas linguagens, pois são as mesmas, a partir deste algoritmo.
Pode-se dizer que: 
a) Todas as afirmativas estão corretas 
b) Todas as afirmativas estão incorretas 
c) Estão corretas as afirmações I e II 
d) Estão corretas as afirmações I, II e III 	Comment by Gabriel Gomes: Como a IV é “meia-boca”(falta informações) a opção mais correta é D) I, II e III
e) Estão corretas as afirmações II e IV 
8-A considerar, como exemplos de expressão regular (ER) e suas linguagens, é correto afirmar que: 
a) (a + b)*, representa todas as cadeias sobre { a, b } 
b) aa, representa somente a cadeia b 	Comment by Gabriel Gomes: Não existe b nesta cadeia de “a’s”
c) ba*, representa cadeias que iniciam com a, seguida por zero ou mais b 	Comment by Gabriel Gomes: Inicia com b e contémrepetição de a
d) a*ba*ba*, representa todas as cadeias contendo exatamente dois a 	Comment by Gabriel Gomes: Cadeias que iniciam a e repetições deste, depois b e repetições de a e por ultimo mais um b e repetições de a
e) ab*, representa cadeias que iniciam com b, seguida por zero ou mais a	Comment by Gabriel Gomes: Inicia com a e contém repetição de b