DC-UFRPE/Licenciatura Plena em Computação/Teoria da Computação/2.5 Equivalência entre ERs e AFNs

Equivalência entre ERs e AFNs

Expressões regulares e autômatos finitos em geral funcionam de maneiras significativamente distintas. Mas será que isso significa que um desses modelos é mais poderoso do que o outro? Qual deles você acha que representa mais linguagens?

Nós vamos provar que esses modelos são todos equivalentes entre si. Como já mostramos a equivalência entre AFDs e AFNs, basta mostrar a equivalência entre um deles e as ERs.

Vamos mostrar isso apresentando as seguintes conversões:

• Conversão de uma ER qualquer para um AFN
• Conversão de um AFD qualquer para uma ER

Conversão de uma ER para AFN

Vamos mostrar, caso a caso, como converter as três expressões básicas e os três operadores que apresentamos na definição de ER.

Todos os autômatos criados pelas conversões terão apenas um estado inicial (obviamente) e um estado de aceitação.

Conversão das expressões básicas

Conversão de expressões básicas

Conversão de expressões básicas

• ai (para um símbolo ai qualquer do alfabeto Е)
• ԑ
• Ǿ (Expressão nula)