II) Autômatos Finitos Não Determinísticos (AFN): Um AFN pode ter múltiplas transições possíveis para o mesmo símbolo, ou até transições vazias (ε).

Apesar de parecerem mais poderosos, os AFNs e AFDs reconhecem exatamente o mesmo conjunto de linguagens: as linguagens regulares.

III) Conversão entre ER, AFN e AFD: Qualquer expressão regular pode ser transformada em um AFN, que pode ser convertido em um AFD.

Isso permite que um compilador, ao receber expressões regulares, construa autômatos que reconhecem tokens.

Gramáticas Regulares

As gramáticas regulares são um subconjunto das gramáticas formais, usadas para descrever linguagens regulares.

São equivalentes às expressões regulares e aos autômatos finitos.

Formato típico de regras: A → aB, B → bC, C → ε

Onde letras maiúsculas são não-terminais, minúsculas são terminais, e ε representa cadeia vazia.

Questões

Exercite seu aprendizado!