[...] Equivalência entre AFD e AFN – Embora um AFN seja somente um acréscimo ao AFD, na verdade não aumenta seu poder computacional, sendo assim, para cada AFN é possível construir um AFD equivalente que realiza o mesmo processamento. O contrário também é verdadeiro. Autômato Finito com Movimentos Vazios – Movimentos vazios constituem uma generalização dos modelos de máquinas não determinísticas, é um movimento determinado por uma simples mudança de estado. Uma das vantagens dos autômatos Finitos com Movimentos Vazios no estudo das linguagens Formais é o fato de facilitar algumas construções e demonstrações relacionadas com os autômatos. Equivalência entre AFN e AFe – Analogamente ao não-determinístico, os movimentos vazios não aumentam o poder computacional dos autômatos finitos. Assim, para cada AFe, é possível construir um AFN que realiza o mesmo processamento. O contrário é trivialmente verdadeiro [...].
Considerando as informações acima, avalie as afirmações a seguir:
I. Um Autômato Finito Determinístico ε, ou Autômato Finito não-Determinístico épsilon é o autômato que contém movimentos épsilon ou movimentos chamados nulos, pois autômatos finitos determinísticos são autômatos finitos com zero.
II. A palavra vazia ε é aceita por um Autômato Finito não Determinístico se houver um estado inicial que também é um estado final, pois quando uma máquina AFN está em um determinado estado e lê um símbolo, a máquina poderá escolher para onde ir em seguida.
III. Para remover o movimento nulo e convertê-lo em AFN, devemos primeiramente considerar os dois vértices tendo o movimento épsilon, pois tanto para AFDs quanto para AFNs, deve-se ler um símbolo para que a máquina faça um movimento.
III, apenas.
I e III, apenas.
II, apenas.
I e II, apenas.
II e III, apenas.