Grammatiche libere dal contesto

[Gjbob]

Devo risolvere esercizi di questo tipo ma sn un po incasinato .

Si dia una grammatica che generi il seguente linguaggio:
{a^m b^n c^k d^h |m > 2h > 0, n != k}



qualcuno di voi sa aiutarmi?

[magix2003]

Credo che troverai più aiuto se scrivi in questa discussione (o chiedi di spostarla a qualche mod):

http://www.hwupgrade.it/forum/showth...321413&page=34

Ciao,

Giorgio

[Vincenzo1968]

Una grammatica libera dal contesto è rappresentata da una quadrupla:

G = {V,T,P,S}

V = insieme delle variabili(simboli non terminali)
T = insieme dei simboli che formano le stringhe del linguaggio(simboli terminali)
P = insieme delle regole che rappresentano la definizione ricorsiva del linguaggio(Produzioni)
S = variabile che rappresenta il linguaggio(simbolo iniziale)

Nel nostro caso:

G = {{S,A,B,C,D}, {a,b,c,d}, P, S}

Rimane da definire l'insieme P delle produzioni. Ma prima vorrei sapere se, per caso, hai dimenticato una virgola.
Cioè, nelle condizioni, dev'essere

m > 2h > 0, n != k

o

m > 2, h > 0, n != k

?

[Gjbob]

La prima, cmq in allegato l'esercizio orign.

[Vincenzo1968]

Il linguaggio

L = {a^m b^n c^k d^h | m > 2h > 0, n != k}

è il linguaggio delle stringhe costituite da un certo numero(m) di a, seguite da un certo numero(n) di b, seguite da un certo numero(k) di c, seguite da un certo numero(h) di d.

le condizioni ci dicono che:

1) il numero di a presenti nella stringa dev'essere maggiore del numero di b moltiplicato per 2 ( m > 2h ).
2) il numero di d dev'essere >= 1 ( implicito in 2h > 0 ); dunque, anche il numero di a dev'essere maggiore di zero.
3) il numero di b dev'essere diverso dal numero di c.

Purtroppo non esiste un algoritmo ben definito per costruire una grammatica. Esistono infiniti modi per definire una grammatica per lo stesso linguaggio. Bisogna dar di tocco alla propria creatività
Una possibile grammatica per generare il nostro linguaggio potrebbe essere la seguente:

S → aaaSd | X
X → U | V 
U → TbU | TbT 
V → TcV | TcT 
T → bTcT | ε

La regola S → aaaSd genera stringhe che soddisfano le condizioni 1 e 2. Le altre regole assicurano che sia soddisfatta anche la terza condizione(n != k).
S, X, U, V e T sono i simboli non terminali; S è il simbolo iniziale. I simboli terminali sono a,b,c e d.
Il simbolo ε indica la stringa vuota.

Abbiamo dunque:

G = {V,T,P,S}

V = insieme delle variabili(simboli non terminali)
T = insieme dei simboli che formano le stringhe del linguaggio(simboli terminali)
P = insieme delle regole che rappresentano la definizione ricorsiva del linguaggio(Produzioni)
S = variabile che rappresenta il linguaggio(simbolo iniziale)

G = {{S,X,U,V,T}, {a,b,c,d}, P, S} dove P, l'insieme delle produzioni, è rappresentato da:

S → aaaSd | X
X → U | V 
U → TbU | TbT 
V → TcV | TcT 
T → bTcT | ε

P.S: lo so, può sembrare una cosa pazzesca e, per certi versi, lo è. Non a caso il primo capitolo del libro di Hopcroft, Motwani e Ullman s'intitola "Automi: metodo e follia".

[mad_hhatter]

non sono sicuro che la produzione S -> aaaSd generi tutte le possibili stringhe in cui le 'a' siano più del doppio delle 'd'. In particolare la stringa parziale 'aaaaaaaaaaSd' è in L, ma non mi pare si riesca a generare con la grammatica proposta. Inoltre potendo S generare anche il solo simbolo X, la grammatica genera stringhe non appartenenti a L.

direi che, considerando per ora solo le a e le d, potremmo scrivere:

S -> AD
A -> Aa | a
D -> aaADd

funziona? (purtroppo non ho tempo di fare dimostrazioni formali)

[Tommy]

Ti propongo anche una mia soluzione (penso vada bene)

S -> aS | aaSd | aaaTd
T -> b | c | bT | Tc

[Vincenzo1968]

Originariamente inviato da mad_hhatter

non sono sicuro che la produzione S -> aaaSd generi tutte le possibili stringhe in cui le 'a' siano più del doppio delle 'd'. In particolare la stringa parziale 'aaaaaaaaaaSd' è in L, ma non mi pare si riesca a generare con la grammatica proposta. Inoltre potendo S generare anche il solo simbolo X, la grammatica genera stringhe non appartenenti a L.

direi che, considerando per ora solo le a e le d, potremmo scrivere:

S -> AD
A -> Aa | a
D -> aaADd

funziona?

Azz, è vero

allora, per P, adottiamo le regole proposte da Tommy (che dovrebbero essere corrette e forniscono una grammatica più compatta)

[mad_hhatter]

Originariamente inviato da Vincenzo1968

Azz, è vero

allora, per P, adottiamo le regole proposte da Tommy (che dovrebbero essere corrette e forniscono una grammatica più compatta)

scusate, non è per rompere i cocomeri, ma la produzione T -> permette di generare la sottostringa bc in cui n = k che è non valido

[Vincenzo1968]

Originariamente inviato da mad_hhatter

scusate, non è per rompere i cocomeri, ma la produzione T -> permette di generare la sottostringa bc in cui n = k che è non valido

E così, potrebbe andar bene?:

S -> aS | aaSd | aaaTd
T -> bbTc | bTcc | ε

Bisognerebbe prevedere, comunque, anche i casi in cui:
- non è presente nessuna b; sono presenti una o più c.
- non è presente nessuna c; sono presenti una o più b.

[mad_hhatter]

no, non va bene perché genera bbbccc

inizio a chiedermi se L, con quel vincolo n <> k, sia un CFL

[Vincenzo1968]

Originariamente inviato da mad_hhatter

no, non va bene perché genera bbbccc

inizio a chiedermi se L, con quel vincolo n <> k, sia un CFL

uhmmm

consideriamo allora la tua grammatica per le a e le d:

S -> AD
A -> Aa | a
D -> aaADd

Dobbiamo aggiungere le produzioni per b e c. Per la produzione T possiamo partire da questa:

T → bTcT | ε

che genera stringhe che contengono un numero uguale di b e di c(giusto?) e aggiungere delle produzioni in modo che n <> k(sempreché, come hai fatto notare, L sia un linguaggio contex free).

[Gjbob]

Intanto ringrazio tutti per l'aiuto, e posto la soluzione ufficale del mio prof.

Il linguaggio è generato dalla categoria sintattica S:

S  --> aaS1d   (genero almeno due a e una d)
S1 --> aaS1d   (genero un numero di a pari al doppio delle d)
S1 --> aS1     (genero un numeo arbitrario di a)
S1 --> aS2     (genero almeno una a)
S2 --> bS2c    (genero tante b quante c)
S2 --> S3      (con queste tre regole genero
S3 --> bS3      un numero arbitrario di b 
S3 --> b        maggiore a zero)
S2 --> S4      (con queste tre regole genero
S4 --> S4c      un numero arbitrario di c 
S4 --> c        maggiore a zero)

mi avete dato una mano ! Cmq se volete continuare nella discu magari capisco qualcosa in +


Vediamo se ho capito:


Si dia una grammatica per generare il seguente linguaggio:
L = {(ab)^n c^2m j n != m}


S --> abS0
S0 --> abS1
S1 --> cS2
S2 --> cc


la sol. ufficiale invece è:

S0 --> abS0cc (inserisco k ab e k cc)

S0 --> S1 
S1 --> abS1
S1 --> ab

S0 --> S2
S2 --> S2cc
S2 --> cc

ci ho capito qualocsa o la mia non funge?

[mad_hhatter]

Originariamente inviato da Gjbob

Intanto ringrazio tutti per l'aiuto, e posto la soluzione ufficale del mio prof.

Il linguaggio è generato dalla categoria sintattica S:

S  --> aaS1d   (genero almeno due a e una d)
S1 --> aaS1d   (genero un numero di a pari al doppio delle d)
S1 --> aS1     (genero un numeo arbitrario di a)
S1 --> aS2     (genero almeno una a)
S2 --> bS2c    (genero tante b quante c)
S2 --> S3      (con queste tre regole genero
S3 --> bS3      un numero arbitrario di b 
S3 --> b        maggiore a zero)
S2 --> S4      (con queste tre regole genero
S4 --> S4c      un numero arbitrario di c 
S4 --> c        maggiore a zero)

che e' errata in quanto non rispetta il famoso vincolo n <> k, oltre a essere inutilmente complessa

per le b e le c forse questa funziona:

T -> bTc | C | B
B -> b | bB
C -> c | Cc

in pratica genero sempre lo stesso numero di b e c (incluso il caso in cui tale numero sia 0) e poi pompo o solo altre c oppure solo altre b.

in questo modo evito la possibilita' che il numero di b e c sia uguale. Funziona?

EDIT: cavolo, e' quello che ha scritto il tuo prof. scusate: tra tutte quelle Si ho fatto confusione e non ho notato la distinzione tra S3 e S4 chiedo scusa 1000 volte

[mad_hhatter]

il secondo esercizio e' analogo e la tua soluzione e' corretta.

chiedo ancora scusa per l'errore nel mio post precedente

[Vincenzo1968]

Grazie per aver postato la soluzione. Prima avevo parlato di follia e stavo, appunto, uscendo pazzo per trovarne una

[Tommy]

Originariamente inviato da mad_hhatter

che e' errata in quanto non rispetta il famoso vincolo n <> k, oltre a essere inutilmente complessa

per le b e le c forse questa funziona:

T -> bTc | C | B
B -> b | bB
C -> c | Cc

in pratica genero sempre lo stesso numero di b e c (incluso il caso in cui tale numero sia 0) e poi pompo o solo altre c oppure solo altre b.

in questo modo evito la possibilita' che il numero di b e c sia uguale. Funziona?

Per il fatto delle b e c funziona..Però si deve vedere come hai scritto la S perchè c'è anche il caso che non ci sono ne b e ne c..

Posto una versione della mia corretta con la tua seconda parte

S -> aS | aaSd | aaaTd | aaad
T -> bTc | B | C
B -> b | bB
C -> c | Cc

[Vincenzo1968]

Originariamente inviato da Tommy

Per il fatto delle b e c funziona..Però si deve vedere come hai scritto la S perchè c'è anche il caso che non ci sono ne b e ne c..

Posto una versione della mia corretta con la tua seconda parte

S -> aS | aaSd | aaaTd | aaad
T -> bTc | B | C
B -> b | bB
C -> c | Cc

Se non ci sono né b né c, non viene soddisfatta la condizione n != k(sarebbe n = k = 0).
Possono essere del tutto assenti le b ma deve esserci almeno una c(o, viceversa, possono non esserci c, ma deve esserci almeno una b).

[Tommy]

Vero vince.. scusate allora..

S -> aS | aaSd | aaaTd
T -> bTc | B | C
B -> b | bB
C -> c | Cc

[Gjbob]

Sempre in tema di esercizi in cui la fantasia non basta mai:


parliamo di automi a stati finiti:


IL testo dell'esercizio recita:

http://img220.imageshack.us/my.php?i...automa1sz3.jpg

la cui soluzione ufficiale è:

L'automa ha 9 stati, con i seguenti significati:

S0: ho letto 4k 'a' e non ho ancora letto nessuna 'c'
S1: ho letto 4k+1 'a' e non ho ancora letto nessuna 'c'
S2: ho letto 4k+2 'a' e non ho ancora letto nessuna 'c'
S3: ho letto 4k+3 'a' e non ho ancora letto nessuna 'c'
Z0: ho letto 4k 'a' e ho gia' letto almeno una 'c'
Z1: ho letto 4k+1 'a' e ho gia' letto almeno una 'c'
Z2: ho letto 4k+2 'a' e ho gia' letto almeno una 'c'
Z3: ho letto 4k+3 'a' e ho gia' letto almeno una 'c'
E: dopo aver letto almeno una 'c' ho letto almeno una 'b'.

Lo stato iniziale e' S0.
Gli stati di accettazione sono S0 e Z0.
Ho le seguenti transizioni con etichetta 'a':
S0 --a--> S1; S1 --a--> S2; S2 --a--> S3; S3 --a--> S0;
Z0 --a--> Z1; Z1 --a--> Z2; Z2 --a--> Z3; Z3 --a--> Z0;
E --a--> E.
Ho le seguenti transizioni con etichetta 'b':
S0 --b--> S0; S1 --b--> S1; S2 --b--> S2; S3 --b--> S3;
Z0 --b--> E; Z1 --b--> E; Z2 --b--> E; Z3 --b--> E;
E --b--> E.
Ho le seguenti transizioni con etichetta 'c':
S0 --c--> Z0; S1 --c--> Z1; S2 --c--> Z2; S3 --c--> Z3;
Z0 --c--> Z0; Z1 --c--> Z1; Z2 --c--> Z2; Z3 --c--> Z3;
E --c--> E.
Ho le seguenti transizioni con etichetta 'd':
S0 --d--> S0; S1 --d--> S1; S2 --d--> S2; S3 --d--> S3;
Z0 --d--> Z0; Z1 --d--> Z1; Z2 --d--> Z2; Z3 --d--> Z3;
E --d--> E.

Quello ke mi kiedo io è:

come è possibile che lo stato S0 sia stato iniziale e di accettazione??

Per ora io sono giunto a questa soluzione :

http://img120.imageshack.us/my.php?image=automa2go3.jpg