Aqui vai um ex. para a produção de ERs a partir de autômatos. Ele é trabalhoso e muito sujeito a erros, assim que não vai para uma lista obrigatória. Tem duas partes, baseadas numa questão da prova. Com alfabeto {a,b}, seja A o conjunto das palavras com número ímpar de A's e B o conjunto das palavras com número par de B's. É fácil construir AD's com dois estados para cada uma dessas linguagens.
- A prova pediu uma ER para a união de A e B. A partir daqueles autômatos, produza um para a união. Existem dois jeitos:
- Tratar os dois como ANDs.
- Fazer o produto cartesiano.
No primeiro caso, qualquer um dos algoritmos produz uma expressão simples. Já no segundo...
Considere agora
interseção de A e B. Aqui não tem jeito, tem que usar o produto.
Esses vários autômatos com 4 estados dão uma boa dura nos vários algoritmos, e devem ajudar vocês a ver se entenderam mesmo. Dá para usar o jflap para comparar.