[OT] Grammatiche libere dal contesto

[gokan]

Salve ragazzi, sono alle prese con un esame di Informatica Teorica ed ho qualche dubbio sulla risoluzione di qualche esercizio
sulle grammatiche libere dal contesto (CFG).
L'esercizio dice che dato un linguaggio L={(a^n)(b^2n)(c^k)|n>=1,k>=1}, devo costruire una CFG che generi tale linguaggio.
Io l'ho risolvo così: creo prima di tutto una grammatica che generi le stringhe della forma (a^n)(b^2n), cioè A->abb|aAbb
Poi creò una grammatica che generi tutte le stringhe di c (B->cB|c) .A questo punto metto assieme le due grammatiche nell'assioma S->AB
In definitiva la grammatica cercata è:
S->AB
A->abb|aAbb
B->cB|c

Infatti le produzioni seguenti generano stringhe appartenenti al linguaggio L:
S=>AB=>aAbbB=>aAbbcB=>aaAbbbbcB=>aaAbbbbcc=>aaabbbbbbcc

Se dovessi costruire una grammatica che generi il linguaggio L={(a^2n)(c^k)(b^n)(c^h)|n>=1,k>=1,h>=1}, come mi devo muovere?
La difficoltà sta nel fatto che questa volta (a^2n) e (b^n) sono divisi da (c^k), quindi risulta più complicato tenerli legati.

[anx721]

Si usa lo stesso meccanismo che hai usato tu steso nell'altro esempio, con una piccola modifica:

S -> AC
A -> aaAb | C
C -> cC | c

Dal simbolo iniziale generi AC; da A applicando la prima produzione per n volte generi la (a^2n)C(b^n) da cui generi (a^2n)(c^k)(b^n) applicando le produzioni per C,

Ciao.

[gokan]

Grazie tante
Adesso me la vado a studiare e ti faccio sapere se ho capito tutto.
Grazie ancora.

[gokan]

Di nuovo grazie. Tutto Ok

[gokan]

u,v appartengono a {a,b}*
Devo sapere quale dei due linguaggi è context-free ed in quel caso devo fornire una grammatica adeguata al linguaggio.
Sono quasi certo che L2 sia context-free, devo riuscire a trovare una grammatica che generi questo linguaggio. L1 penso che non sia context-free e questo si dimostra attraverso il lemma di iterazione (noto anche come pumping lemma)

[anx721]

L1 = u(a^n)(b^m)v è context-free ; la seguente grammatica lo genera (lamda è la parola vuota):

S -> UABV
U -> Uuu | lamda
V -> Vvvv| lambda
A -> aA | a
B -> bB | b

U genera stringhe con un numero di u multiplo di 2; V genera stringhe con un numero di v multiplo di 3; A genera stringhe con un numero di a maggiore di uno; B genera stringhe con un numero di b multiplo di 3, quindi S genera il linguaggio.

L'altro non penso proprio sia acontstuale, ciao.

[gokan]

Originariamente inviato da anx721
L1 = u(a^n)(b^m)v è context-free ; la seguente grammatica lo genera (lamda è la parola vuota):

S -> UABV
U -> Uuu | lamda
V -> Vvvv| lambda
A -> aA | a
B -> bB | b

U genera stringhe con un numero di u multiplo di 2; V genera stringhe con un numero di v multiplo di 3; A genera stringhe con un numero di a maggiore di uno; B genera stringhe con un numero di b multiplo di 3, quindi S genera il linguaggio.

L'altro non penso proprio sia acontstuale, ciao.

Grazie Anx, ci sono arrivato in altro modo, ho visto che la tua grammatica è più pulita di quella che avevo pensato io. Questa dovrebbe essere l'ultima volta che ti disturbo per queste cose