Autómato finito generalizado (AFG)

Nos autómatos finitos apresentados as transições entre estados apenas decorrem de símbolos do alfabeto ou, no caso dos AFND, da palavra vazia (ε).

No entanto podemos aproximar ainda mais os autómatos finitos das expressões regulares fazendo com que as transições possam decorrer de ER (nas quais os símbolos do alfabeto e a palavra vazia são casos elementares).

Este tipo de autómatos designa-se por Autómato finito generalizado (AFG).

Por exemplo, um AFG sobre o alfabeto A ={a;b;c} para o conjunto de palavras que contém a palavra aba será:

AFG reduzido

Um AFG com a forma

designa-se por autómato finito generalizado reduzido.

Note que:

• O estado A não é de aceitação e não tem arcos a chegar de outros estados.

• O estado B é de aceitação e não tem arcos a sair.

Se reduzir um AFG à forma anterior a expressão – e – é uma expressão regular equivalente ao autómato.

Conversão de uma AFG numa ER

Assim transformar uma AFG num AFG reduzido corresponde a determinar a ER que lhe é equivalente.

Algoritmo de conversão:

1. Transformação de um AFG noutro cujo estado inicial não tenha arcos a chegar.

   1. Se necessário, acrescenta-se um novo estado inicial com um arco em ε para o antigo.

2. Transformação de um AFG noutro com um único estado de aceitação, sem arcos de saída.

   1. Se necessário, acrescenta-se um novo estado, que passa a ser o único de aceitação, que recebe arcos em ε dos anteriores estados de aceitação, que deixam de o ser.

3. Eliminação dos restantes estados.

   1. Os estados são eliminados um a um, em processos de transformação que mantêm a equivalência.

Conversão de uma AFG numa ER: Exemplo

Recuperando o AFG atrás apresentado vamos aplicar este algoritmo para o transformar numa ER.

Aplicando a regra 1:

Aplicando a regra 2:

Eliminando o estado A aplicando a regra 3:

Eliminando o estado B aplicando a regra 3:

Eliminar estado com arcos a chegar de outros estados

Se for necessário eliminar um estado que seja destino de arcos de outros estados, é necessário garantir – nesses estados – que o caminho de reconhecimento garantido pelo estado a eliminar não se altera.

Considerando que (e1;e2;e3;e4) são ER, a eliminação de estado A do AFG

resulta no seguinte AFG:

Conversão de uma AFG numa ER: Exemplo 2

Obtenha uma ER equivalente ao AF seguinte:

Regras 1 e 2:

Eliminar o estado A pela regra 4:

Finalmente, eliminar o estado B pela regra 3:

Logo a ER equivalente será: 0*1(0 j 10*1)*