Prévia do material em texto

Aula 2 - Autômatos finitos não determinísticos 
1. Uma cadeia de entrada a1a2 ...an é aceita/reconhecida por um AFND se existe AO 
MENOS UMA sequência de transições que leva do estado inicial para algum estado 
final. 
Nesse contexto, sobre os AFND, assinale a alternativa correta. 
a) Os AFNDs permitem que uma mesma transição atinja dois estados diferentes, 
limitando a análise que possa ser realizada para cada símbolo de entrada. 
b) Um AFND tem uma cadeia aceita se, pelo menos, um estado final é atingido ao 
final do processamento, lembrando que o autômato pode ter mais de um estado 
final. 
c) Pelo fato de o AFND ser mais generalista, ele tem um poder de expressão 
relativamente maior que o AFD, pois a quantidade de AFNDs acaba sendo bem 
maior que a de AFDs. 
d) É possível realizar conversões de AFNDs para AFDs, mas o AFND em questão não 
poderá ter uma transição vazia, o que impossibilitaria tal conversão entre eles. 
e) Sejam a e b o alfabeto de entrada de um AFND, pode-se inferir que, em um 
AFND, para cada estado, será realizada uma única transição com base em um 
símbolo de entrada. 
2. As tabelas AFN ajudam a ter uma visão de cada transição com base no estado atual, 
símbolo de entrada e estado(s) alvo(s). 
Observe o diagrama AFN a seguir: 
 
Assinale a alternativa que apresenta corretamente a tabela AFN correspondente ao AFN. 
 
 
A. 
 
B. 
 
. 
C. 
 
 
 
D. 
 
E. 
 
 
3. A definição formal de um AFN é composta basicamente de uma 5-upla, cuja notação 
pode ser dada por: 
M=(Ʃ, Q, δ,q0,F) 
Em que Ʃé o alfabeto, Q o conjunto de estados, q0 o estado inicial e F o conjunto de 
estados finais. 
Considere o seguinte AFN, em que: 
Ʃ = (a, b); 
F = {q2}. 
 
Analise as afirmativas: 
I. O AFN tem transições vazias para q2. 
II. O AFN em questão aceita todas as cadeias iniciadas por a ou b. 
III. O AFN em questão termina, necessariamente, com dois símbolos iguais. 
IV. O AFN aceita cadeias de, no mínimo, dois caracteres. 
É correto o que se afirma nos itens: 
a) I e II, apenas. 
b) III e IV, apenas. 
c) I, III e IV, apenas. 
d) II, III e IV, apenas. 
e) I, II e III, apenas. 
 
4. Os AFNs podem ser convertidos em AFDs equivalentes com base em algumas regras 
de acordo com o estado atual, símbolo de entrada e próximo estado. Observe o AFN a 
seguir: 
 
Que autômato finito determinístico aceita a mesma linguagem? 
A. 
 
B. 
 
C. 
 
D. 
 
E. É impossível converter esse autômato finito não determinístico em um autômato 
finito determinístico. 
 
5.A notação formal relacionada a um AFN tem por objetivo, além de sua devida 
formalização, instruir sobre características e estado da computação atual do autômato. 
Considere que determinada computação de um AFN esteja na seguinte situação para a 
entrada 011: 
 
Com base nessa tabela, pode-se afirmar que: 
 
A. ao ler o símbolo 1, quando em q0, o autômato permanece apenas em q0. 
B. A computação está no estado q0 e q1 em "paralelo", avaliando o símbolo 0. 
C. A computação chegou a seu estado final, e a cadeia foi aceita. 
D. Ao ser lido um símbolo 1 no estado q1, o AFN vai para q0. 
E. Independentemente da entrada, quando em q0, o autômato vai para q1.