[Informatica teorica] Generare una grammatica da un linguaggio

[mistergks]

Ho difficoltà a fare esercizi del tipo:
Dato un linguaggio generare una grammatica.
Ad esempio il linguaggio
L={a^n | b } con n>=0;

Come genero una sua grammatica? Ci sono regole precise? Perche sui libri non trovo nulla di preciso
Potrebbe andare:
S-> aS | b
B-> b

???

[sharkkk]

Ho difficoltà a fare esercizi del tipo:
Dato un linguaggio generare una grammatica.
Ad esempio il linguaggio
L={a^n | b } con n>=0;

Come genero una sua grammatica? Ci sono regole precise? Perche sui libri non trovo nulla di preciso
Potrebbe andare:
S-> aS | b
B-> b

???

Credo che quel linguaggio generi:

S-> A | b
A-> aA | e

[mistergks]

Credo che quel linguaggio generi:

S-> A | b
A-> aA | e

Perche? Come si fa? Esiste un modo per verificare che sia giusto?

[sharkkk]

Perche? Come si fa? Esiste un modo per verificare che sia giusto?

è la stessa domanda che mi sto ponendo anche io con un mio compagno di corso.

noi facciamo cosi, prendiamo delle stringhe generate da quel linguaggio e vediamo se la grammatica generata le soddisfa costruendo l'albero.

tipo le stringhe:
- e -> S-> A , A-> e
- b -> S-> b
- a -> S-> A , A-> aA , A-> e
- aa -> S-> A , A-> aA , A-> aA, A-> e

tutto corretto, quindi la grammatica generata dovrebbe essere quella giusta

[mistergks]

Non ho capito :confused:
Quest'Albero come funziona?

[british]

Ho difficoltà a fare esercizi del tipo:
Dato un linguaggio generare una grammatica.
Ad esempio il linguaggio
L={a^n | b } con n>=0;

Come genero una sua grammatica? Ci sono regole precise? Perche sui libri non trovo nulla di preciso


Regole generali per un linguaggio in generale non mi risulta esistano. Esistono per la famiglia dei linguaggi regolari.
In generale si va a diciamo a intuito, poggiandosi magari a una base di linguaggi "noti", qualche esempio:

linguaggio delle liste { a^n }
S -> A
A -> Aa | a

linguaggio lista con separatori {a}.{xa}*
S -> AL
L -> XAL | XA
X -> x
A -> a

linguaggio palindromi { xx^R } con x in {a,b}*
P -> aPa | bPb | e