[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]

Originariamente inviato da 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

???

Credo che quel linguaggio generi:

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

[mistergks]

Originariamente inviato da sharkkk

Credo che quel linguaggio generi:

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

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

[sharkkk]

Originariamente inviato da mistergks

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
Quest'Albero come funziona?

[british]

Originariamente inviato da 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

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