Toda gramática inequívoca é regular?

Sep 15 2020

Enquanto procurava uma resposta a esta pergunta, descobri que existe uma gramática inequívoca para cada idioma regular. Mas existe uma linguagem regular para cada gramática inequívoca? Como posso provar que isso é / não é verdade?

Respostas

12 YuvalFilmus Sep 15 2020 at 18:14

A gramática a seguir não é ambígua, mas gera uma linguagem não regular: $$ S \to aSb \mid \epsilon $$