[grammatiche] dubbio su esericizio

[simo9115]

salve a tutti.
mi devo preparare per l'esame di fondamenti d'informatica e ho qualche problema con questo esercizio:
Dato il linguaggio $L = {a^nbcd^n | n >=0 }$:
-E’ possibile utilizzare una grammatica regolare? Se si, dare la sua definizione.

come faccio a rispondere a questa domanda? dalle slide fornite non riesco a venirne a capo...
grazie

[onlyReferee]

Ciao simo9115
No, una grammatica regolare per generare questo linguaggio non la si può trovare in quanto il linguaggio non è di tipo tre. Si può fornire una grammatica di tipo due volendo. Se scrivi le produzioni di tale grammatica noterai come queste non rispettano i vincoli imposti da quelle di tipo tre.

[simo9115]

Ciao simo9115
No, una grammatica regolare per generare questo linguaggio non la si può trovare in quanto il linguaggio non è di tipo tre. Si può fornire una grammatica di tipo due volendo. Se scrivi le produzioni di tale grammatica noterai come queste non rispettano i vincoli imposti da quelle di tipo tre.

ok grazie dell'aiuto senti hai qualche dispensa per questo tipo di argomento? io purtroppo nn sono riuscito a trovare niente di semplice...tutte formule che mi complicano la vita...

[onlyReferee]

In realtà ci possono essere dispense scritte più o meno. Parlare di formule che complicano la vita mi sembra un attimo eccessivo (al massimo quella del pumping lemma è un attimo più elaborata ma nulla di eccezionale secondo me).
In ogni caso se mi mandi la tua mail in privato ti posso inviare la parte della mia tesi che tratta questi argomenti.

[simo9115]

In realtà ci possono essere dispense scritte più o meno. Parlare di formule che complicano la vita mi sembra un attimo eccessivo (al massimo quella del pumping lemma è un attimo più elaborata ma nulla di eccezionale secondo me).
In ogni caso se mi mandi la tua mail in privato ti posso inviare la parte della mia tesi che tratta questi argomenti.

inviato