Generare grammatica da pattern
Ciao a tutti,
ho un esercizio che mi chiede di generare una grammatica da un pattern, ma non so proprio come fare... Il testo dell'esercizio dice:
"Si definisca una grammatica che generi le stringhe su {a,b,c} aventi il seguente pattern $(aba)^n(bab)(c)^n$ con $n>0$.
So fare l'inverso, ovvero determinare il pattern a partire dalle regole della grammatica ma questo esercizio non saprei come risolverlo...
ho un esercizio che mi chiede di generare una grammatica da un pattern, ma non so proprio come fare... Il testo dell'esercizio dice:
"Si definisca una grammatica che generi le stringhe su {a,b,c} aventi il seguente pattern $(aba)^n(bab)(c)^n$ con $n>0$.
So fare l'inverso, ovvero determinare il pattern a partire dalle regole della grammatica ma questo esercizio non saprei come risolverlo...
Risposte
Ciao 
Allora, intanto per capire bene come procedere sapresti dire dal pattern di che tipo è la grammatica di cui dobbiamo determinare le regole
Detto ciò, una volta che determiniamo il tipo della grammatica sappiamo la forma che devono avere le nostre regole e possiamo determinarle di conseguenza. Abbiamo sicuramente un simbolo iniziale (che possiamo chiamare $S$) di cui dobbiamo determinare la/le produzione/i. Essendo $bab$ contornato sia a sinistra che a destra da gruppi di simboli aventi lo stesso esponente la nostra idea può essere quella di espandere un singolo simbolo non terminale (diverso da quello iniziale).
Vedrai che appena determini la soluzione scoprirai che è più semplice di ciò che sembra
.
Allora, intanto per capire bene come procedere sapresti dire dal pattern di che tipo è la grammatica di cui dobbiamo determinare le regole
Detto ciò, una volta che determiniamo il tipo della grammatica sappiamo la forma che devono avere le nostre regole e possiamo determinarle di conseguenza. Abbiamo sicuramente un simbolo iniziale (che possiamo chiamare $S$) di cui dobbiamo determinare la/le produzione/i. Essendo $bab$ contornato sia a sinistra che a destra da gruppi di simboli aventi lo stesso esponente la nostra idea può essere quella di espandere un singolo simbolo non terminale (diverso da quello iniziale).
Vedrai che appena determini la soluzione scoprirai che è più semplice di ciò che sembra
.
"onlyReferee":
Ciao
Allora, intanto per capire bene come procedere sapresti dire dal pattern di che tipo è la grammatica di cui dobbiamo determinare le regole
Detto ciò, una volta che determiniamo il tipo della grammatica sappiamo la forma che devono avere le nostre regole e possiamo determinarle di conseguenza. Abbiamo sicuramente un simbolo iniziale (che possiamo chiamare $S$) di cui dobbiamo determinare la/le produzione/i. Essendo $bab$ contornato sia a sinistra che a destra da gruppi di simboli aventi lo stesso esponente la nostra idea può essere quella di espandere un singolo simbolo non terminale (diverso da quello iniziale).
Vedrai che appena determini la soluzione scoprirai che è più semplice di ciò che sembra
Dal pattern non riesco a capire il tipo della grammatica...
Ti do un aiuto: può essere di tipo tre Prova a pensare a quanto abbiamo scritto nell'altro thread riguardo alla classificazione di Chomsky.
Prova a pensare a quanto abbiamo scritto nell'altro thread riguardo alla classificazione di Chomsky.
"onlyReferee":
Ti do un aiuto: può essere di tipo tre
Allora, una grammatica è di tipo 3 se, considerando sempre \( \alpha \rightarrow \beta \) , $alpha$ ha un simbolo non terminale e $beta$ deve avere un simbolo terminale oppure un terminale seguito da un non terminale.
Solo che in questo pattern non riesco a capire come si può determinare la grammatica senza poter vedere le regole...
Basta che provi a rispondere a questa domanda: si può disegnare un automa deterministico per riconoscere il linguaggio descritto Se la risposta è sì allora la grammatica è di tipo tre, se è no...
Se la risposta è sì allora la grammatica è di tipo tre, se è no...
"onlyReferee":
Basta che provi a rispondere a questa domanda: si può disegnare un automa deterministico per riconoscere il linguaggio descritto
Se disegno l'automa mi viene un automa non deterministico, in quanto ho più transazioni che vanno in uno stato. Quindi è una grammatica di tipo 2? Solo in questo modo si può verificare il tipo della grammatica a partire dal pattern? In ogni caso dopo aver determinato la grammatica come scrivo le regole?
Se riesci posta anche il disegno dell'automa. In realtà questo è un trucco che viene con l'esperienza e permette di capire subito se un linguaggio può essere generato o meno con una grammatica di tipo tre. In ogni caso basta che noti il fatto che è necessario "memorizzare" il valore di $n$ per poter generare i gruppi di simboli, fatto che come sappiamo non è possibile nei linguaggi di tipo tre.
Le regole le puoi scrivere nel modo seguente: $$S \rightarrow A\\A \rightarrow abaAc | ...$$
Completa te ciò che ci va al posto dei puntini.
Le regole le puoi scrivere nel modo seguente: $$S \rightarrow A\\A \rightarrow abaAc | ...$$
Completa te ciò che ci va al posto dei puntini.
"onlyReferee":
Se riesci posta anche il disegno dell'automa. In realtà questo è un trucco che viene con l'esperienza e permette di capire subito se un linguaggio può essere generato o meno con una grammatica di tipo tre. In ogni caso basta che noti il fatto che è necessario "memorizzare" il valore di $n$ per poter generare i gruppi di simboli, fatto che come sappiamo non è possibile nei linguaggi di tipo tre.
Le regole le puoi scrivere nel modo seguente: $$S \rightarrow A\\A \rightarrow abaAc | ...$$
Completa te ciò che ci va al posto dei puntini.
Allora io ho fatto così, in quanto in alcuni risultati di esercizi che avevo riportava così la risoluzione, se riesci dimmi se ho fatto in modo corretto
Allora questo è l'automa (sempre se è corretto
):
Poi ho scritto le transizioni dell'automa:
\( q{_0}a\rightarrow q_{1} \)
\( q{_1}a\rightarrow q_{1} \)
\( q{_1}b\rightarrow q_{2} \)
\( q{_2}b\rightarrow q_{2} \)
\( q{_2}a\rightarrow q_{1} \)
\( q{_2}c\rightarrow q_{3} \)
\( q{_3}c\rightarrow q_{3} \)
Ora per convertirlo in grammatica sposto la lettera dell'alfabeto a destra e se lo stato e iniziale o finale aggiungo un nuovo stato cancellando lo stato di destra, in questo modo:
\( q{_0}\rightarrow aq_{1} \)
\( q{_1}\rightarrow aq_{1} \)
\( q{_1}\rightarrow bq_{2} \)
\( q{_2}\rightarrow bq_{2} \)
\( q{_2}\rightarrow aq_{1} \)
\( q{_2}\rightarrow cq_{3} \)
\( q{_3}\rightarrow cq_{3} \)
$+$
\( q{_0}\rightarrow a \)
\( q{_3}\rightarrow c \)
E' corretto?
No, l'automa non riconosce il linguaggio richiesto purtroppo. Con questo automa infatti potresti riconoscere il linguaggio $a^{\star}b^{\star}c^{\star}$ che però non corrisponde a quello richiesto. Il fatto è che nemmeno un automa non deterministico si riesce a trovare per un linguaggio di tipo due. Al massimo si può determinare un automa a pila che però è qualcosa di diverso dall'automa che siamo solitamente abituati a conoscere.
Per questo motivo il procedimento di partire sempre e comunque cercando di costruire un automa deterministico/non deterministico che riconosca il linguaggio dato non è corretto.
Per questo motivo il procedimento di partire sempre e comunque cercando di costruire un automa deterministico/non deterministico che riconosca il linguaggio dato non è corretto.
"onlyReferee":
No, l'automa non riconosce il linguaggio richiesto purtroppo. Con questo automa infatti potresti riconoscere il linguaggio $a^{\star}b^{\star}c^{\star}$ che però non corrisponde a quello richiesto. Il fatto è che nemmeno un automa non deterministico si riesce a trovare per un linguaggio di tipo due. Al massimo si può determinare un automa a pila che però è qualcosa di diverso dall'automa che siamo solitamente abituati a conoscere.
Per questo motivo il procedimento di partire sempre e comunque cercando di costruire un automa deterministico/non deterministico che riconosca il linguaggio dato non è corretto.
Quindi come sarebbe dovuto essere l'automa?
Dovremmo fare una lezione apposita solo sugli automi a pila 
.
Il mio consiglio è comunque quello di scrivere direttamente le regole della grammatica per questo tipo di esercizi. Il fatto di capire a priori la tipologia delle regole della grammatica è solo per avere un'idea della struttura che possono appunto avere le regole di produzione. Prova a completare le regole che avevo iniziato a scriverti in uno degli ultimi post.
.Il mio consiglio è comunque quello di scrivere direttamente le regole della grammatica per questo tipo di esercizi. Il fatto di capire a priori la tipologia delle regole della grammatica è solo per avere un'idea della struttura che possono appunto avere le regole di produzione. Prova a completare le regole che avevo iniziato a scriverti in uno degli ultimi post.
"onlyReferee":
Se riesci posta anche il disegno dell'automa. In realtà questo è un trucco che viene con l'esperienza e permette di capire subito se un linguaggio può essere generato o meno con una grammatica di tipo tre. In ogni caso basta che noti il fatto che è necessario "memorizzare" il valore di $n$ per poter generare i gruppi di simboli, fatto che come sappiamo non è possibile nei linguaggi di tipo tre.
Le regole le puoi scrivere nel modo seguente: $$S \rightarrow A\\A \rightarrow abaAc | ...$$
Completa te ciò che ci va al posto dei puntini.
$$S \rightarrow A\\A \rightarrow abaAc | bab$$
corretto?
No. Ci vuole $abababc$. Nel caso "minimo" ti devi fermare alla generazione di una sola occorrenza per i gruppi di vari simboli (c'è $n > 0$ tra i vincoli).
"onlyReferee":
No. Ci vuole $abababc$. Nel caso "minimo" di devi fermare alla generazione di una sola occorrenza per i gruppi di vari simboli (c'è $n > 0$ tra i vincoli).
Non riesco a capire purtroppo da dove viene fuori
Prova a disegnarti un piccolo albero delle ricorsioni sia con la tua che con la mia versione e poi confronta i risultati. La tua soluzione sarebbe corretta con $n \ge 0$ ma non lo è in questo caso proprio per il motivo che ti dicevo. La tua versione permette di generare la stringa $bab$ (senza gli altri gruppi di simboli terminali a sinistra ed a destra) che però non è inclusa nel nostro linguaggio. Per questo non va bene.
"onlyReferee":
Prova a disegnarti un piccolo albero delle ricorsioni sia con la tua che con la mia versione e poi confronta i risultati. La tua soluzione sarebbe corretta con $n \ge 0$ ma non lo è in questo caso proprio per il motivo che ti dicevo. La tua versione permette di generare la stringa $bab$ (senza gli altri gruppi di simboli terminali a sinistra ed a destra) che però non è inclusa nel nostro linguaggio. Per questo non va bene.
Io non riesco a capire una cosa, ovvero, qual è il metodo da seguire quando si ha un pattern per poter ricavare la grammatica? Bisogna disegnare un automa di quel pattern? Non riesco a venirne fuori
sto cercando su mille libri e online ma non riesco a trovare nulla che mi aiuti a parte il tuo prezioso aiuto qui sul forum.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo