Grammatica libera dal contesto

[magsas]

Salve community,
sto cercando qualcuno disposto ad aiutarmi nel risolvere questo esercizio sulle grammatiche libere dal contesto. Io sto impazzendo e non riesco a trovare la soluzione.

L'esercizio dice: "Sia Σ={a,b}. Mostrare una grammatica context-free per il linguaggio L={a^m b^h | m, h >= 0, m>h e m diverso da 2h}.

Ringrazio tutti anticipatamente.

[Marinelli]

Spostato nella sezione dedicata alla scuola.

Intanto tu non arrenderti e magari prova a postare qualche soluzione a cui arrivi, anche se non corretta.

Ciao ;)

[magsas]

Ok, inizio io. La soluzione migliore a cui sono arrivato è questa:

S -> aaSb | A
A -> aA | epsilon


Quindi, riesco a calcolare le parole formate da tutte a e quelle dove la b non supera la metà delle a

Restano da calcolare le parole dove la b è compresa fra la metà +1 delle a e il numero delle a -1.

[magsas]

Con queste produzioni dovrei aver risolto il problema per le parole dove |a| è dispari

S-> aC
C -> aaCbB | epsilon
B -> b | epsilon


Quindi, restano da generare le parole dove |a| > 2h e m > h..................

[Marinelli]

Ciao.
Io sono un po' arrugginito, ma ho comunque provato e ho ottenuto una grammatica. Non sarà molto elegante, ma dovrebbe essere una soluzione al problema:


S -> aP | M
P -> aaPb | aP | eps
M -> aaaNbb
N -> aaNb | aNb | eps


Non so se lo conosci già, ma ti segnalo comunque JFLAP: http://www.cs.duke.edu/csed/jflap/

Ciao :)

[magsas]

Ti ringrazio Marinelli, sia per la grammatica sia per la segnalazione di jflap. Scusami il ritardo, ma avevo perso le speranze che qualcuno mi rispondesse e non tenevo più d'occhio la discussione. Ciaooo

[Homra]

scusate l'ignoranza ma che roba è???

[ndakota]

scusate l'ignoranza ma che roba è???

Si studiano in informatica e in linguistica. Nel mio corso di laurea, informatica, sono previste nel corso "linguaggi formali e automi".

[Ciccio17]

scusate l'ignoranza ma che roba è???

Se vuoi farti un'idea --> http://it.wikipedia.org/wiki/Grammatica_formale

[Marinelli]

Ti ringrazio Marinelli, sia per la grammatica sia per la segnalazione di jflap. Scusami il ritardo, ma avevo perso le speranze che qualcuno mi rispondesse e non tenevo più d'occhio la discussione. Ciaooo

Figurati, ciao ;)