Question

Sobre Autômatos finitos não determinísticos (AFND), analise as afirmativas a seguir:

I- Os autômatos finitos não determinísticos são reconhecedores das linguagens livres de contexto, assim ao terminar de ler uma palavra, se o estado que leu o último símbolo for um estado final, isso significa que a cadeia foi reconhecida.

II- Todo Autômato finito não determinístico pode ser transformado em um autômato finito determinístico equivalente;

III- No autômato finito não determinístico pode-se se ter somente um estado final e n estados iniciais;

Agora, assinale a alternativa que apresenta a resposta CORRETA:

Selecione uma alternativa:
a)
Apenas a alternativa I está correta;

b)
Apenas a alternativa II está correta;

c)
Apenas as alternativas I e II estão corretas;

d)
Apenas as alternativas I e III estão corretas;

e)
As alternativas I, II e III estão corretas.

Answer 1

Sobre Autômatos finitos não determinísticos (AFND), as afirmativas a seguir são:

I - Correta: Os autômatos finitos não determinísticos conseguem reconhecer certas linguagens livres de contexto. Assim ao terminar de ler uma palavra, se o estado que leu o último símbolo for um estado final, isso significa que a cadeia foi reconhecida.

II - Correta: todo Autômato finito não determinístico (AFND-ε) pode ser transformado em um AFND equivalente, assim como todo AFND pode ser transformado em um  autômato finito determinístico (AFD) equivalente, pelo método chamado de construção do conjunto de potência.

III - Correta: o autômato finito não determinístico  é baseado em uma função de transição, que recebe de um estado inicial uma cadeia de caracteres pertencentes ao alfabeto (a entrada), e que está lendo essa cadeia à medida que o autômato se move de um estado para outro, para finalmente pare em um estado final ou de aceitação.

Alternativa correta: e)  As alternativas I, II e III estão corretas.