Grammatica libera e generazione di un linguaggio

[Gremo]

Ciao a tutti, qualcuno ha idea di come rispondere a queste due domandine? :mbe:

1) Caratterizzare il linguaggio generato dalla grammatica
2) Dire se la grammatica è ambigua (cioè trovare una stringa che ammetta due alberi di parsing diversi)

Qualcuno ha idea di come devo procedere? La descrizione della grammatica è questa:


S -> A | AS | BR | CT
R -> AR | BT | C | CS
T -> AT | B | BS | CR

e

A -> 0 | 3 | 6 | 9
B -> 1 | 4 | 7
C -> 2 | 5 | 8

[_Claudio]

Ciao a tutti, qualcuno ha idea di come rispondere a queste due domandine? :mbe:

1) Caratterizzare il linguaggio generato dalla grammatica
2) Dire se la grammatica è ambigua (cioè trovare una stringa che ammetta due alberi di parsing diversi)

Qualcuno ha idea di come devo procedere? La descrizione della grammatica è questa:


S -> A | AS | BR | CT
R -> AR | BT | C | CS
T -> AT | B | BS | CR

e

A -> 0 | 3 | 6 | 9
B -> 1 | 4 | 7
C -> 2 | 5 | 8



Per quanto riguarda la caratterizzazione basta verificare che non genera stringhe simmetriche di lunghezza a piacere o altre particolarità non esprimibili con i linguaggi regolari (sovrainsieme di quelli finiti).
In questo caso ad occhiata veloce posso dirti che quello definito è un linguaggio regolare in quanto le stringhe generate sono tipo liste e le sue regole sono lineari destre.

Essendo poi una grammatica libera da contesto, senza traduzioni quindi, per la ricerca delle ambiguità bisogna procedere empiricamente perchè esse non sono formalizzabili.
Quelle che conosco sono:
-ricorsione bilaterale: no
-unione: no
-concatenamento: no
-codici univoci: non è questo il caso
-generazione equivoca: non mi pare ve ne siano
-delle frasi condizionali: non ci sono ricorsioni doppie quindi niente

A mio avviso dopo un'occhiata veloce ti direi che hai ottenuto un linguaggio regolare e privo di ambiguità.