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[editar | editar código-fonte]
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[editar | editar código-fonte]
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[editar | editar código-fonte]
- ai (para um símbolo ai qualquer do alfabeto Е)
- ԑ
- Ǿ (Expressão nula)