Esempi sui tipi di regole grammaticali
Ciao a tutti, sono alle prese con la grammatica di Chomsky e sto studiando i tipi di regole grammaticali ma non riesco ad applicarle a casi pratici. Qualcuno potrebbe farmi un esempio pratico per ogni tipo di regola? Come faccio a definire a quale tipo di regola fa riferimento ad una grammatica o linguaggio?
Tipo 0 ----- $ alpha in A^{\star} - T^{\star} $ ----- General
Tipo 1 ----- Tipo 0 + $|alpha| <= |beta|$ ----- context-sensitive
Tipo 2 ----- Tipo 1 + $ alpha in A - T $ ----- context-free
Tipo 3 ----- Tipo 2 + $ beta in T + T(A-T) $ ----- right-linear
Con A = Alfabeto, T = Simboli Terminali, S = Simboli di Start, R = Regole
Tipo 0 ----- $ alpha in A^{\star} - T^{\star} $ ----- General
Tipo 1 ----- Tipo 0 + $|alpha| <= |beta|$ ----- context-sensitive
Tipo 2 ----- Tipo 1 + $ alpha in A - T $ ----- context-free
Tipo 3 ----- Tipo 2 + $ beta in T + T(A-T) $ ----- right-linear
Con A = Alfabeto, T = Simboli Terminali, S = Simboli di Start, R = Regole
Risposte
Ciao 
Ti ho allegato intanto lo screenshot di un pdf che ho dove le varie tipologie di grammatiche sono spiegate molto bene. Prova a vedere se a partire da queste riesci intanto a costruire degli esempi.
In generale comunque, dato che secondo la gerarchia di Chomsky i linguaggi di tipo tre sono contenuti in quelli di tipo due e così via verso l'alto (ed appare subito che tutti i linguaggi sono almeno di tipo zero), conviene vedere man mano quali vincoli rispetta la grammatica del linguaggio dato a partire da quello di tipo uno. In questo modo ci si ferma non appena si arriva al tipo tre oppure quando si vede che le regole non si adattano più ai vincoli richiesti.
Ti ho allegato intanto lo screenshot di un pdf che ho dove le varie tipologie di grammatiche sono spiegate molto bene. Prova a vedere se a partire da queste riesci intanto a costruire degli esempi.
In generale comunque, dato che secondo la gerarchia di Chomsky i linguaggi di tipo tre sono contenuti in quelli di tipo due e così via verso l'alto (ed appare subito che tutti i linguaggi sono almeno di tipo zero), conviene vedere man mano quali vincoli rispetta la grammatica del linguaggio dato a partire da quello di tipo uno. In questo modo ci si ferma non appena si arriva al tipo tre oppure quando si vede che le regole non si adattano più ai vincoli richiesti.
"onlyReferee":
Ciao
Ti ho allegato intanto lo screenshot di un pdf che ho dove le varie tipologie di grammatiche sono spiegate molto bene. Prova a vedere se a partire da queste riesci intanto a costruire degli esempi.
In generale comunque, dato che secondo la gerarchia di Chomsky i linguaggi di tipo tre sono contenuti in quelli di tipo due e così via verso l'alto (ed appare subito che tutti i linguaggi sono almeno di tipo zero), conviene vedere man mano quali vincoli rispetta la grammatica del linguaggio dato a partire da quello di tipo uno. In questo modo ci si ferma non appena si arriva al tipo tre oppure quando si vede che le regole non si adattano più ai vincoli richiesti.
Ciao!
ti ringrazio per lo screenshot ora provo a guardarmelo per bene... ma come faccio a determinare un linguaggio di che tipo è? Per definizione: "un linguaggio è di tipo 'i' se può essere generato da una grammatica di tipo 'i' e non può essere generato da una grammatica di tipo 'i+1'" Quindi se ho una grammatica di tipo 2, (ciò vuol dire che per esempio essa è formata da regole di tipo 2 e 3 corretto?) allora il linguaggio sarà anch'esso di tipo 2?
-------
P.S.: Per esempio ho un esercizio del genere:
Data la seguente grammatica:
S -> BC
B -> cBa
C -> bCa
B -> ca
C -> ba
di simbolo terminali {a,b,c} e non terminali {S,B,C} (S iniziale), si specifichi il tipo di tale grammatica e si dia il pattern del linguaggio che essa genera.
Grammatica di tipo x genera linguaggi che sono di tipo x. Poi per la gerarchia di Chomsky se un linguaggio é di tipo x allora per forza è anche di tipo x - 1 in quanto le regole della sua grammatica soddisfano anche i requisiti del tipo x - 1.
Pertanto in ciò che hai scritto l'unica affermazione non corretta è quella tra parentesi in quanto una grammatica di tipo due è formata da regole di tipo due (che poi soddisfino anche i requisiti di quelle di tipo uno è una diretta conseguenza).
Pertanto in ciò che hai scritto l'unica affermazione non corretta è quella tra parentesi in quanto una grammatica di tipo due è formata da regole di tipo due (che poi soddisfino anche i requisiti di quelle di tipo uno è una diretta conseguenza).
"onlyReferee":
Grammatica di tipo x genera linguaggi che sono di tipo x. Poi per la gerarchia di Chomsky se un linguaggio é di tipo x allora per forza è anche di tipo x - 1 in quanto le regole della sua grammatica soddisfano anche i requisiti del tipo x - 1.
Pertanto in ciò che hai scritto l'unica affermazione non corretta è quella tra parentesi in quanto una grammatica di tipo due è formata da regole di tipo due (che poi soddisfino anche i requisiti di quelle di tipo uno è una diretta conseguenza).
Ma il tipo di una grammatica non è determinato dal minore tipo delle regole ad essa legate?
"A grammar G is of type i with i ∈ {0,1,2,3} if i is the minimum of the proper types which can be assigned to the rules of G."
Per quanto riguarda l'esercizio da me postato sopra io l'ho risolto così:
Il tipo della grammatica è il TIPO 3 perchè è generata da regole del tipo: A->aB oppure A->a con A,B € A e a € T. Il linguaggio sarà anch'esso di TIPO 3.
Il pattern del linguaggio che essa genera è del tipo (a^n)(b^m)(c^m) con n,m € N e con n,m > 0. Questo risultato l'ho ricavato svolgendo appunto tutte le regole della grammatica ottenendo una stringa: ccaabbaa.
E' corretto?
Il tipo della grammatica è il TIPO 3 perchè è generata da regole del tipo: A->aB oppure A->a con A,B € A e a € T. Il linguaggio sarà anch'esso di TIPO 3.
Il pattern del linguaggio che essa genera è del tipo (a^n)(b^m)(c^m) con n,m € N e con n,m > 0. Questo risultato l'ho ricavato svolgendo appunto tutte le regole della grammatica ottenendo una stringa: ccaabbaa.
E' corretto?
"JoKeRxbLaCk":
Ma il tipo di una grammatica non è determinato dal minore tipo delle regole ad essa legate?
"A grammar G is of type i with i ∈ {0,1,2,3} if i is the minimum of the proper types which can be assigned to the rules of G."
Fonte di questa informazione
Se ciò fosse vero tutte le grammatiche sarebbero di tipo zero dato che, stando a ciò che c'è scritto, questo è il minimo tipo che può essere assegnato alle regole di una grammatica 
."JoKeRxbLaCk":
Per quanto riguarda l'esercizio da me postato sopra io l'ho risolto così:
Il tipo della grammatica è il TIPO 3 perchè è generata da regole del tipo: A->aB oppure A->a con A,B € A e a € T. Il linguaggio sarà anch'esso di TIPO 3.
Il pattern del linguaggio che essa genera è del tipo (a^n)(b^m)(c^m) con n,m € N e con n,m > 0. Questo risultato l'ho ricavato svolgendo appunto tutte le regole della grammatica ottenendo una stringa: ccaabbaa.
E' corretto?
Nell'esempio di grammatica da te proposto se procedi verificando le regole delle stessa rispetto ai requisiti dei tipi zero, uno, ecc, vedi che la stessa è di tipo due e non tre (ciascuna produzione presuppone che ci sia un unico simbolo non terminale nella parte sinistra della regola). Tra l'altro nessuna delle produzioni della grammatica rispetta i requisiti richiesti per le regole delle grammatiche di tipo tre.
"onlyReferee":
[quote="JoKeRxbLaCk"]
Ma il tipo di una grammatica non è determinato dal minore tipo delle regole ad essa legate?
"A grammar G is of type i with i ∈ {0,1,2,3} if i is the minimum of the proper types which can be assigned to the rules of G."
Fonte di questa informazione
Se ciò fosse vero tutte le grammatiche sarebbero di tipo zero dato che, stando a ciò che c'è scritto, questo è il minimo tipo che può essere assegnato alle regole di una grammatica ."JoKeRxbLaCk":
Per quanto riguarda l'esercizio da me postato sopra io l'ho risolto così:
Il tipo della grammatica è il TIPO 3 perchè è generata da regole del tipo: A->aB oppure A->a con A,B € A e a € T. Il linguaggio sarà anch'esso di TIPO 3.
Il pattern del linguaggio che essa genera è del tipo (a^n)(b^m)(c^m) con n,m € N e con n,m > 0. Questo risultato l'ho ricavato svolgendo appunto tutte le regole della grammatica ottenendo una stringa: ccaabbaa.
E' corretto?
Nell'esempio di grammatica da te proposto se procedi verificando le regole delle stessa rispetto ai requisiti dei tipi zero, uno, ecc, vedi che la stessa è di tipo due e non tre (ciascuna produzione presuppone che ci sia un unico simbolo non terminale nella parte sinistra della regola). Tra l'altro nessuna delle produzioni della grammatica rispetta i requisiti richiesti per le regole delle grammatiche di tipo tre.[/quote]
Infatti avevo anche io questo dubbio sulle regole delle grammatiche seguendo quella definizione, però quella definizione viene dal mio libro di testo universitario... Che nella sua totalità è così:
"According to the previous classification, types are inclusive, in the sense that a rule of type i+1 satisfies the conditions of type i, but the proper type of a rule is the maximum type which we can assign to it. A grammar G is of type i with i ∈ {0,1,2,3} if i is the minimum of the proper types which can be assigned to the rules of G. A language is of type i if it can be generated by a grammar of type i. It is properly of type i (i < 3) if it is generated by a grammar of type i and cannot be generated by a grammar of type i+1."
Per quanto riguarda l'esercizio da me postato , il fatto che abbiamo delle regole che ad un simbolo non terminale associano dei simboli terminali e non , non dovrebbe essere indice di una grammatica di tipo 3, da come ho scritto prima? Non riesco a capire
Il pattern da me scritto sarebbe comunque corretto?
P.S.: Cioè ho una grammatica di tipo 2 quando a destra e sinistra ho solo un simbolo, mentre è di tipo 3 quando a destra e sinistra ho due simboli? Può essere visto così?
Difatti penso sia stato scritto un "minimum" al posto di un "maximum" nella definizione (e purtroppo di errori di questo tipo ve ne sono anche nei testi universitari. Prima infatti recita correttamente: "but the proper type of a rule is the maximum type which we can assign to it".
Venendo all'esercizio: no, non può essere tipo tre perché appunto ci sono delle regole (nella fattispecie tutte quante) che non rispettano i vincoli imposti alle regole di produzione (la grammatica non è né regolare destra né regolare sinistra). Ti basta considerare anche semplicemente la produzione per il simbolo iniziale $S \rightarrow BC$. Questa non è né nella forma $B \rightarrow aB$, né in quella $B \rightarrow Ba$ né in $B \rightarrow a$. Se noti ciò è spiegato bene nel file che ti ho allegato.
Il pattern del linguaggio è $c^na^nb^ma^m$ con $n, m > 0$. Per convincerti ancora di più del fatto che questo linguaggio sia di tipo due ti basti sapere che se questo fosse ti tipo tre riusciresti ad ottenere un automa finito deterministico che è in grado di riconoscerlo. Ciò però è chiaramente impossibile poiché un automa finito non ha memoria e per tale motivo non è in grado di memorizzare il numero di $c$ e conseguentemente riconoscere lo stesso numero di $a$ (lo stesso dicasi per le lettere $b$ ed $a$). Ciò si può fare invece con un automa a pila che è difatti utilizzato per riconoscere linguaggi di tipo due.
Venendo all'esercizio: no, non può essere tipo tre perché appunto ci sono delle regole (nella fattispecie tutte quante) che non rispettano i vincoli imposti alle regole di produzione (la grammatica non è né regolare destra né regolare sinistra). Ti basta considerare anche semplicemente la produzione per il simbolo iniziale $S \rightarrow BC$. Questa non è né nella forma $B \rightarrow aB$, né in quella $B \rightarrow Ba$ né in $B \rightarrow a$. Se noti ciò è spiegato bene nel file che ti ho allegato.
Il pattern del linguaggio è $c^na^nb^ma^m$ con $n, m > 0$. Per convincerti ancora di più del fatto che questo linguaggio sia di tipo due ti basti sapere che se questo fosse ti tipo tre riusciresti ad ottenere un automa finito deterministico che è in grado di riconoscerlo. Ciò però è chiaramente impossibile poiché un automa finito non ha memoria e per tale motivo non è in grado di memorizzare il numero di $c$ e conseguentemente riconoscere lo stesso numero di $a$ (lo stesso dicasi per le lettere $b$ ed $a$). Ciò si può fare invece con un automa a pila che è difatti utilizzato per riconoscere linguaggi di tipo due.
"onlyReferee":
Difatti penso sia stato scritto un "minimum" al posto di un "maximum" nella definizione (e purtroppo di errori di questo tipo ve ne sono anche nei testi universitari. Prima infatti recita correttamente: "but the proper type of a rule is the maximum type which we can assign to it".
Venendo all'esercizio: no, non può essere tipo tre perché appunto ci sono delle regole (nella fattispecie tutte quante) che non rispettano i vincoli imposti alle regole di produzione (la grammatica non è né regolare destra né regolare sinistra). Ti basta considerare anche semplicemente la produzione per il simbolo iniziale $S \rightarrow BC$. Questa non è né nella forma $B \rightarrow aB$, né in quella $B \rightarrow Ba$ né in $B \rightarrow a$. Se noti ciò è spiegato bene nel file che ti ho allegato.
Il pattern del linguaggio è $c^na^nb^ma^m$ con $n, m > 0$. Per convincerti ancora di più del fatto che questo linguaggio sia di tipo due ti basti sapere che se questo fosse ti tipo tre riusciresti ad ottenere un automa finito deterministico che è in grado di riconoscerlo. Ciò però è chiaramente impossibile poiché un automa finito non ha memoria e per tale motivo non è in grado di memorizzare il numero di $c$ e conseguentemente riconoscere lo stesso numero di $a$ (lo stesso dicasi per le lettere $b$ ed $a$). Ciò si può fare invece con un automa a pila che è difatti utilizzato per riconoscere linguaggi di tipo due.
Ti ringrazio per le mille risposte che mi stai dando
Non capisco però come mai il pattern è $c^na^nb^ma^m$ con $n, m > 0$ e non $c^na^nb^na^m$, ovvero perchè 'b' e l'ultima 'a' hanno lo stesso esponente?
P.S.: Penso di aver capito il mio ultimo quesito, perchè durante lo svolgimento delle regole della grammatica 'c' e 'a' crescono in modo simmetrico tra di loro mentre 'b' e l'altra 'a' crescono in modo simmetrico tra di loro, ma non hanno nulla a che vedere con le altre due. Corretto?
Di nulla, figurati .
Per il semplice fatto che se osservi le produzioni di $C$ vedi come quando viene generata una $b$ sia prodotta anche una $a$ corrispondente.
Nota a tal proposito che $C$ e $B$ viaggiano in maniera indipendente nelle produzioni e pertanto questo giustifica la diversità dei due esponenti $m$ ed $n$.
.Per il semplice fatto che se osservi le produzioni di $C$ vedi come quando viene generata una $b$ sia prodotta anche una $a$ corrispondente.
Nota a tal proposito che $C$ e $B$ viaggiano in maniera indipendente nelle produzioni e pertanto questo giustifica la diversità dei due esponenti $m$ ed $n$.
"onlyReferee":
Di nulla, figurati
Per il semplice fatto che se osservi le produzioni di $C$ vedi come quando viene generata una $b$ sia prodotta anche una $a$ corrispondente.
Nota a tal proposito che $C$ e $B$ viaggiano in maniera indipendente nelle produzioni e pertanto questo giustifica la diversità dei due esponenti $m$ ed $n$.
Nel file che mi hai allegato la grammatica è così definita: G = {V, A, P, S} dove P = Produttorie / Regole, S = Start, A = alfabeto? e V = simboli terminali?.
Non so perchè ma non riesco proprio a capire come riconoscere i tipi delle grammatiche...
-------
Allora vediamo se sono riuscito a capire qualcosa
Secondo il mio libro di testo ho una grammatica così definita: G = {A,T,S,R} , con A = alfabeto, T = simboli terminali, S = start, R = regole.
La relazione principale è $ alpha -> beta $.
Supponiamo per poter fare degli esempi che A = {a,b,c,d,A,B,C,D} e che T = {a,b,c,d}.
Una regola di TIPO 0, fa sì che $alpha in A^{\star} - T^{\star}$ ovvero che $alpha$ deve appartenere a cosa?
Una regola di TIPO 1, fa si che valga la regola di TIPO 0 + che $|alpha| <= |beta|$ e fin qui ci sono.
Una regola di TIPO 2, fa si che valga la regola di TIPO 1 + $alpha in A-T$ quindi che $alpha$ contenga {A,B,C,D}.
Una regola di TIPO 3, fa si che valga la regola di TIPO 2 + $beta in T + T(A-T)$ quindi $beta$ deve appartenere a cosa?
Questi sono forse i miei dubbi che mi rendono difficile capire l'identificazione del tipo di grammatica.
So che A* = all'insieme delle sequenze finite di simboli su A, quindi se A = {a,b,c,d,A,B,C,D} , A* = {aA, aB, cD, aa, ab, ac, ad, AA, BB, CC, DD, ....} corretto?
"JoKeRxbLaCk":
Nel file che mi hai allegato la grammatica è così definita: G = {V, A, P, S} dove P = Produttorie / Regole, S = Start, A = alfabeto? e V = simboli terminali?.
Non so perchè ma non riesco proprio a capire come riconoscere i tipi delle grammatiche...
[...]
Tranquillo, all'inizio è molto facile fare confusione e questi argomenti richiedono spesso molti esempi per essere compresi a pieno
. Quando ho iniziato a cimentarmi con questi argomenti non è stato immediato nemmeno per me, poi ovviamente ci vuole anche esperienza per prendere dimestichezza con tutto e vedere la soluzione in maniera più rapida e sicura.Comunque $A$ è un alfabeto finito e non vuoto di simboli terminali (quelli che solitamente sono indicati con lettera maiuscola). $V$ è invece un insieme di simboli non terminali detti semplicemente variabili (quelli che solitamente sono indicati con lettera minuscola). Ovviamente deve valere che $A \cap V = \emptyset$ altrimenti sussiste ambiguità nelle regole.
"JoKeRxbLaCk":
-------
Allora vediamo se sono riuscito a capire qualcosa
Secondo il mio libro di testo ho una grammatica così definita: G = {A,T,S,R} , con A = alfabeto, T = simboli terminali, S = start, R = regole.
La relazione principale è $ alpha -> beta $.
Supponiamo per poter fare degli esempi che A = {a,b,c,d,A,B,C,D} e che T = {a,b,c,d}.
Una regola di TIPO 0, fa sì che $alpha in A^{\star} - T^{\star}$ ovvero che $alpha$ deve appartenere a cosa?
Una regola di TIPO 1, fa si che valga la regola di TIPO 0 + che $|alpha| <= |beta|$ e fin qui ci sono.
Una regola di TIPO 2, fa si che valga la regola di TIPO 1 + $alpha in A-T$ quindi che $alpha$ contenga {A,B,C,D}.
Una regola di TIPO 3, fa si che valga la regola di TIPO 2 + $beta in T + T(A-T)$ quindi $beta$ deve appartenere a cosa?
Questi sono forse i miei dubbi che mi rendono difficile capire l'identificazione del tipo di grammatica.
So che A* = all'insieme delle sequenze finite di simboli su A, quindi se A = {a,b,c,d,A,B,C,D} , A* = {aA, aB, cD, aa, ab, ac, ad, AA, BB, CC, DD, ....} corretto?
$\alpha \rightarrow \beta$ è semplicemente un modo per indicare una generica regola di produzione (senza considerare per ora i vincoli imposti dai vari tipi di grammatica). Ora penso di aver intuito il motivo della difficoltà di comprensione: praticamente il tuo libro nell'alfabeto $A$ contempla sia i simboli terminali che quelli non terminali ed in $T$ invece soltanto quelli terminali (pessima idea secondo me).
Il vincolo espresso per le regole di tipo zero ti dice semplicemente che nella parte sinistra della produzione (ossia per quanto riguarda il nostro $\alpha$ della regola di produzione generica $\alpha \rightarrow \beta$) devi avere solo simboli non terminali (e questo è coerente in quanto di fatto non pone vincoli particolari alle produzioni).
Si comprende abbastanza semplicemente anche il vincolo per il tipo uno, il quale afferma che non possono esserci regole in cui viene diminuita la lunghezza della produzione, ergo sono vietate le $\epsilon$-produzioni eccetto in casi particolari (come mi sembra che tu abbia capito).
Per il tipo due viene imposto di avere un solo simbolo non terminale a sinistra della produzione (e questo mi sembra semplice da comprendere).
Infine per il tipo tre le produzioni devono essere come per il tipo due con l'aggiunta che a destra dobbiamo avere o un simbolo terminale oppure un terminale seguito da un non terminale. Qui però, intudendo da ciò che hai trascritto, il libro è un attimo restrittivo perché considera solo le grammatiche regolari destre. Per questo tipo di grammatiche sono ammesse infatti anche le produzioni $\beta \rightarrow (A - T) T$ oltre a quelle da te già citate (per le grammatiche regolari sinistre). Nota comunque che per essere tipo tre una grammatica non deve essere contemporaneamente sia regolare destra che regolare sinistra. In questo modo ora tutta la definizione è completa
.
"onlyReferee":
[quote="JoKeRxbLaCk"]
Nel file che mi hai allegato la grammatica è così definita: G = {V, A, P, S} dove P = Produttorie / Regole, S = Start, A = alfabeto? e V = simboli terminali?.
Non so perchè ma non riesco proprio a capire come riconoscere i tipi delle grammatiche...
[...]
Tranquillo, all'inizio è molto facile fare confusione e questi argomenti richiedono spesso molti esempi per essere compresi a pieno
. All'inizio non è stato immediato nemmeno per me, poi ovviamente ci vuole anche esperienza per prendere dimestichezza con tutto e vedere la soluzione in maniera più rapida e sicura.Comunque $A$ è un alfabeto finito e non vuoto di simboli terminali (quelli che solitamente sono indicati con lettera maiuscola). $V$ è invece un insieme di simboli non terminali detti semplicemente variabili (quelli che solitamente sono indicati con lettera minuscola). Ovviamente deve valere che $A \cap V = \emptyset$ altrimenti sussiste ambiguità nelle regole.
"JoKeRxbLaCk":
-------
Allora vediamo se sono riuscito a capire qualcosa
Secondo il mio libro di testo ho una grammatica così definita: G = {A,T,S,R} , con A = alfabeto, T = simboli terminali, S = start, R = regole.
La relazione principale è $ alpha -> beta $.
Supponiamo per poter fare degli esempi che A = {a,b,c,d,A,B,C,D} e che T = {a,b,c,d}.
Una regola di TIPO 0, fa sì che $alpha in A^{\star} - T^{\star}$ ovvero che $alpha$ deve appartenere a cosa?
Una regola di TIPO 1, fa si che valga la regola di TIPO 0 + che $|alpha| <= |beta|$ e fin qui ci sono.
Una regola di TIPO 2, fa si che valga la regola di TIPO 1 + $alpha in A-T$ quindi che $alpha$ contenga {A,B,C,D}.
Una regola di TIPO 3, fa si che valga la regola di TIPO 2 + $beta in T + T(A-T)$ quindi $beta$ deve appartenere a cosa?
Questi sono forse i miei dubbi che mi rendono difficile capire l'identificazione del tipo di grammatica.
So che A* = all'insieme delle sequenze finite di simboli su A, quindi se A = {a,b,c,d,A,B,C,D} , A* = {aA, aB, cD, aa, ab, ac, ad, AA, BB, CC, DD, ....} corretto?
$\alpha \rightarrow \beta$ è semplicemente un modo per indicare una generica regola di produzione (senza considerare per ora i vincoli imposti dai vari tipi di grammatica). Ora penso di aver intuito il motivo della difficoltà di comprensione: praticamente il tuo libro nell'alfabeto $A$ contempla sia i simboli terminali che quelli non terminali ed in $T$ invece soltanto quelli terminali (pessima idea secondo me).
Il vincolo espresso per le regole di tipo zero ti dice semplicemente che nella parte sinistra della produzione (ossia per quanto riguarda il nostro $\alpha$ della regola di produzione generica $\alpha \rightarrow \beta$) devi avere solo simboli non terminali (e questo è coerente in quanto di fatto non pone vincoli particolari alle produzioni).
Si comprende abbastanza semplicemente anche il vincolo per il tipo uno, il quale afferma semplicemente che non possono esserci regole in cui viene diminuita la lunghezza della produzione, ergo sono vietate le $\epsilon$-produzione eccetto in casi particolari (come mi sembra che tu abbia capito).
Per il tipo due viene imposto di avere un solo simbolo non terminale a sinistra della produzione (e questo mi sembra semplice da comprendere).
Infine per il tipo tre le produzioni devono essere come per il tipo due con l'aggiunta che a destra dobbiamo avere o un simbolo terminale oppure un terminale seguito da un non terminale. Qui però, intudendo da ciò che hai trascritto, il libro è un attimo restrittivo perché considera solo le grammatiche regolari destre. Per questo tipo di grammatiche sono ammesse infatti anche le produzioni $\beta \rightarrow (A - T) T$ oltre a quelle da te già citate (per le grammatiche regolari sinistre). Nota comunque che per essere tipo tre una grammatica non deve essere contemporaneamente sia regolare destra che regolare sinistra. In questo modo ora tutta la definizione è completa
.[/quote]Allora, per il tipo uno tu dici questo:
"Si comprende abbastanza semplicemente anche il vincolo per il tipo uno, il quale afferma semplicemente che non possono esserci regole in cui viene diminuita la lunghezza della produzione, ergo sono vietate le $\epsilon$-produzione eccetto in casi particolari (come mi sembra che tu abbia capito)."
Ovvero che devo per forza avere B -> $beta$ e la parte sinistra deve sempre esistere, corretto?
Per il tipo tre invece:
"Infine per il tipo tre le produzioni devono essere come per il tipo due con l'aggiunta che a destra dobbiamo avere o un simbolo terminale oppure un terminale seguito da un non terminale."
Questa affermazione dice che: B -> a oppure B -> aC, è corretto? solo in questi due casi? Quindi non è corretto dire che una regola di tipo 3 è la seguente: C -> bCa, giusto?
Se è così mi sembra di aver capito tutto finalmente
"JoKeRxbLaCk":
Allora, per il tipo uno tu dici questo:
"Si comprende abbastanza semplicemente anche il vincolo per il tipo uno, il quale afferma semplicemente che non possono esserci regole in cui viene diminuita la lunghezza della produzione, ergo sono vietate le $\epsilon$-produzione eccetto in casi particolari (come mi sembra che tu abbia capito)."
Ovvero che devo per forza avere B -> $beta$ e la parte sinistra deve sempre esistere, corretto?
La parte sinistra esiste sempre e comunque altrimenti la regola non è proprio definita
. A sinistra devo avere almeno una variabile (unitamente ad altre variabili ed eventuali simboli terminali), a destra posso avere sia variabili che simboli terminali. Gli unici veri e pochi vincoli sulle regole del tipo uno riguardano appunto soltanto la lunghezza della parte destra."JoKeRxbLaCk":
Per il tipo tre invece:
"Infine per il tipo tre le produzioni devono essere come per il tipo due con l'aggiunta che a destra dobbiamo avere o un simbolo terminale oppure un terminale seguito da un non terminale."
Questa affermazione dice che: B -> a oppure B -> aC, è corretto? solo in questi due casi? Quindi non è corretto dire che una regola di tipo 3 è la seguente: C -> bCa, giusto?
Se è così mi sembra di aver capito tutto finalmente
Questo è esatto
"onlyReferee":
[quote="JoKeRxbLaCk"]
Allora, per il tipo uno tu dici questo:
"Si comprende abbastanza semplicemente anche il vincolo per il tipo uno, il quale afferma semplicemente che non possono esserci regole in cui viene diminuita la lunghezza della produzione, ergo sono vietate le $\epsilon$-produzione eccetto in casi particolari (come mi sembra che tu abbia capito)."
Ovvero che devo per forza avere B -> $beta$ e la parte sinistra deve sempre esistere, corretto?
La parte sinistra esiste sempre e comunque altrimenti la regola non è proprio definita
. A sinistra devo avere almeno una variabile (unitamente ad altre variabili ed eventuali simboli terminali), a destra posso avere sia variabili che simboli terminali. Gli unici veri e pochi vincoli sulle regole del tipo uno riguardano appunto soltanto la lunghezza della parte destra."JoKeRxbLaCk":
Per il tipo tre invece:
"Infine per il tipo tre le produzioni devono essere come per il tipo due con l'aggiunta che a destra dobbiamo avere o un simbolo terminale oppure un terminale seguito da un non terminale."
Questa affermazione dice che: B -> a oppure B -> aC, è corretto? solo in questi due casi? Quindi non è corretto dire che una regola di tipo 3 è la seguente: C -> bCa, giusto?
Se è così mi sembra di aver capito tutto finalmente
Qusato è esatto
[/quote]Ti ringrazio sei stato davvero gentile!
Ho un altro esercizio per verificare se ho capito bene
Allora data la seguente grammatica:
S -> BC
B -> acBaa
C -> bcCcb
B -> acaa
C -> bccb
di simboli terminali {a,b,c} e non terminali {S,B,C} (S iniziale), si specifichi il tipo di tale grammatica e il pattern del linguaggio che essa genera.
Allora per prima cosa determino il tipo della grammatica.
Vi sono regole del TIPO 0.
Vi sono regole del TIPO 1: in quanto $|alpha| <= |beta|$
Vi sono regole di TIPO 2: in quanto $alpha$ ha un solo simbolo non terminale.
Ma non vi è una regola di TIPO 3.
Quindi la grammatica è del TIPO 2.
Il pattern che essa genere è:
$(ac)^na^n(bc)^nc^nb^n$
dato che sviluppa una stringa: $acacaaaabcbcccbb$
corretto?
Allora data la seguente grammatica:
S -> BC
B -> acBaa
C -> bcCcb
B -> acaa
C -> bccb
di simboli terminali {a,b,c} e non terminali {S,B,C} (S iniziale), si specifichi il tipo di tale grammatica e il pattern del linguaggio che essa genera.
Allora per prima cosa determino il tipo della grammatica.
Vi sono regole del TIPO 0.
Vi sono regole del TIPO 1: in quanto $|alpha| <= |beta|$
Vi sono regole di TIPO 2: in quanto $alpha$ ha un solo simbolo non terminale.
Ma non vi è una regola di TIPO 3.
Quindi la grammatica è del TIPO 2.
Il pattern che essa genere è:
$(ac)^na^n(bc)^nc^nb^n$
dato che sviluppa una stringa: $acacaaaabcbcccbb$
corretto?
Il tipo individuato è corretto ed il pattern è quasi esatto però c'è un errore che speravo di non vedere. Al posto di $a^n$ hai $(aa)^n$ (altrimenti scrivibile anche come $a^{2n}$), al posto di $c^nb^n$ hai $(cb)^m$ ed al posto di $(bc)^n$ hai $(bc)^m$.
Purtroppo l'errore più lampante è quello di non aver notato che gli esponenti da usare sono diversi per i simboli terminali che genera $B$ e quelli che genera $C$
...
Purtroppo l'errore più lampante è quello di non aver notato che gli esponenti da usare sono diversi per i simboli terminali che genera $B$ e quelli che genera $C$
...
"onlyReferee":
Il tipo individuato è corretto ed il pattern è quasi esatto però c'è un errore che speravo di non vedere. Al posto di $a^n$ hai $(aa)^n$ (altrimenti scrivibile anche come $a^{2n}$), al posto di $c^nb^n$ hai ${cb}^m$ ed al posto di $(bc)^n$ hai $(bc)^m$.
Purtroppo l'errore più lampante è quello di non aver notato che gli esponenti da usare sono diversi per i simboli terminali che genera $B$ e quelli che genera $C$
Hai ragione sono andato sparato e non ci ho fatto caso
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo