[C++/JAVA] Esercizio d'esame

[luvaio]

Salve a tutti,
devo risolvere il quesito qui riportato,
purtroppo non so neanche da dove cominciare (STO IMPAZZENDO VVoVe: )
è esame cruciale , non vi chiedo di risolvermi totalmente il problema ma di potermi indicare come e dove cominciare...

grazie a tutti.
-----------------------------------------------------------

Membership per un linguaggio di tipo 1.
Scrivere e documentare un programma in Java o in C++ che data una grammatica G di tipo 1
e una parola w veri chi se w appartiene al linguaggio L(G) generato da G.
Si ricorda che una grammatica e` di tipo 1 se e solo se le sue produzioni sono del tipo:
stringa1 ! stringa2
ove: (i) stringa1 e stringa2 sono stringhe di terminali e non-terminali, e (ii) la lunghezza di
stringa2 e` maggiore o uguale a quella di stringa1.
Si ricorda anche che per la ricerca di un nodo in un albero di possibili alternative, si puo`
usare lo schema di backtracking.

-----------------------------------------------------------

[mr.smile]

Beh... come quesito è abbastanza vago, ma non mi sembra così difficile se uno riesce a capire il significato delle informazioni.

Sicuramente il prof. avrà spiegato bene cosa sia il tipo1. Quel punto esclamativo per cosa sta? Concatenazione? Non credo vero?

Cosa sai dirci di più!?

[luvaio]

ciao :master: ,
allora per tipo 1 mi riferisco alla grammatica chomsky per quanto riguarda la loro classificazione .
questo è un esame di automi linguaggi e traduttori.

il punto esclamativo doveva essere una "freccia"
cioè STRINGA1 -> STRINGA2 (->="implica").

grazie .

intanto se siete cosi gentili e di animo nobile vi chiedo se mi potete dare una mano anche per quest'altra traccia:


Parsing per un linguaggio di tipo 2.
Scrivere e documentare un programma in Java o in C++ che data una grammatica G di tipo 2
(o context-free) e una parola w ne faccia il parsing.


grazie ancora!!

[unomichisiada]

Originariamente inviato da luvaio
Salve a tutti,
devo risolvere il quesito qui riportato,
purtroppo non so neanche da dove cominciare (STO IMPAZZENDO VVoVe: )
è esame cruciale , non vi chiedo di risolvermi totalmente il problema ma di potermi indicare come e dove cominciare...

grazie a tutti.
-----------------------------------------------------------

Membership per un linguaggio di tipo 1.
Scrivere e documentare un programma in Java o in C++ che data una grammatica G di tipo 1
e una parola w veri chi se w appartiene al linguaggio L(G) generato da G.
Si ricorda che una grammatica e` di tipo 1 se e solo se le sue produzioni sono del tipo:
stringa1 ! stringa2
ove: (i) stringa1 e stringa2 sono stringhe di terminali e non-terminali, e (ii) la lunghezza di
stringa2 e` maggiore o uguale a quella di stringa1.
Si ricorda anche che per la ricerca di un nodo in un albero di possibili alternative, si puo`
usare lo schema di backtracking.

-----------------------------------------------------------

Se non ricordo male una parola appartiene ad un linguaggio definito su una grammatica se è possibile trovare una serie di regole di produzione della grammatica che conducano dal simbolo iniziale della grammatica alla parola stessa (che ovviamente sarà composta di soli simboli terminali della grammatica).

Quindi alcuni consigli potrebbero essere:
-Per prima cosa verifica la parola carattere per carattere la parola w e se non contiene solo e soltanto simboli terminali della grammatica scartala come NON appartente al linguaggio.
(In realtà potresti vedere come buone anche le parole contenenti anche simboli NON terminali interpretandole come insiemi di parole, ma le cose si complicherebbero, per ora te lo sconsiglio).

-Il modo per risolvere il tuo esercizio credo sia procedere in senso inverso,cioè per riduzione: partire dalla parola e cercare di arrivare al solo simbolo start mediante applicazioni successive delle regole di produzione.In altre parole devi usare la ricorsione per provare tutte le strade possibili tornando indietro al passo precedente (backtracking) quando ne trovi una che non porta alla soluzione.

Come algoritmo potresti seguire quello in profondità, cioè partire dal primo/i carattere/i applicargli la prima regola di produzione che gli si addica,poi prendere la stringa otetnuta come nuova stringa e cercare la prima regola di produzione che si addica,se non ce n'è tornare indietro ed applicare un'altra regola di produzione e così via finche non si trova la soluzione (successo) o si esplorano tutte le possibilità senza trovarla (termine della ricorsione e insuccesso)