Ogni grammatica univoca è regolare?
Sep 15 2020
Cercando una risposta a questa domanda ho scoperto che esiste una grammatica univoca per ogni lingua normale. Ma esiste una lingua regolare per ogni grammatica non ambigua? Come posso provare che questo è / non è vero?
Risposte
12 YuvalFilmus Sep 15 2020 at 18:14
La seguente grammatica non è ambigua ma genera un linguaggio non regolare: $$ S \to aSb \mid \epsilon $$