Linguaggio derivato da una grammatica context-free
Ciao a tutti,
ho le seguenti produzioni di una grammatica context-free:
1. S::= wcdS
2. S::=bSe
3. S::=s
4. L::=L;S
5. L::=S
devo ottenere il linguaggio associato alla grammatica
Ho ottenuto due linguaggi L(S) e L(L) per poi utilizzarli per ottenere L(G) in questo modo:
L(S)={ $ (wcd)^n $ s | n=>4}
L(L)={ $($ (wcd)^n $ s;)^m$| n=>3 m=>1 }
L(G)={$(bse)^n$| n=>5 s $in$(S$uu$L) }
Ma non sono se va bene.Ho difficoltà a capire come generare il linguaggio dalla grammatica.
Grazie in anticipo.
ho le seguenti produzioni di una grammatica context-free:
1. S::= wcdS
2. S::=bSe
3. S::=s
4. L::=L;S
5. L::=S
devo ottenere il linguaggio associato alla grammatica
Ho ottenuto due linguaggi L(S) e L(L) per poi utilizzarli per ottenere L(G) in questo modo:
L(S)={ $ (wcd)^n $ s | n=>4}
L(L)={ $($ (wcd)^n $ s;)^m$| n=>3 m=>1 }
L(G)={$(bse)^n$| n=>5 s $in$(S$uu$L) }
Ma non sono se va bene.Ho difficoltà a capire come generare il linguaggio dalla grammatica.
Grazie in anticipo.
Risposte
Prima di tutto vorrei far notare che ho principalmente imparato queste cose da solo per cui non so quanto sia in linea con quello che ti ha insegnato il tuo professore. Ma provo comunque a darti una mano.
Normalmente in una grammatica si definisce uno "start symbol", usato per rappresentare l'intera parola. In questo caso sembra essere \(L\). Infatti, se partissimo da \(S\), \(L\) non comparirebbe mai. Non sono poi sicuro del significato del \(;\) nella grammatica. Suppongo sia un simbolo terminale. In tal caso possiamo iniziare a scrivere \(L\) come \( S\,(;\,S)^* \) in cui ho scritto la stringa in funzione soltanto di \(S\) e usato poi i soliti operatori delle espressioni regolari per comodità. In altre parole il tuo linguaggio è formato da 1 o più parole del linguaggio determinato da S separate da un punto e virgola. A questo punto è sufficiente fare la stessa cosa per \(S\)
Siccome questa grammatica non è regolare non posso fare più ricorso alle espressioni regolari. Possiamo però pensare di applicare \(m_1\) volte la prima regole, \(n_1\) la seconda, \(m_2\) la prima.. e fermarci quando finalmente scegliamo la terza regola. Abbiamo quindi che possiamo scrivere \(S\) come
\[ L(S) = \Biggl\{ \Bigl( \prod_{i=1}^I \; (wcd)^{m_i}\,b^{n_i} \Bigr)\,s\,e^N \Biggr. \; \Biggl| \; N = \sum_{i=0}^{I} n_i, \; \forall \; i \in \{ 1, \dotsc I \}. \; m_i \geq 0 \land n_i \geq 0 \Biggr\} \]
A questo punto possiamo infilare questa espressione nella precedente e ottenere:
\[ L(G) = \{ s_0\, (;\, s_i)^n \mid n \geq 0, s_0, s_i \in L(S) \} \]
Normalmente in una grammatica si definisce uno "start symbol", usato per rappresentare l'intera parola. In questo caso sembra essere \(L\). Infatti, se partissimo da \(S\), \(L\) non comparirebbe mai. Non sono poi sicuro del significato del \(;\) nella grammatica. Suppongo sia un simbolo terminale. In tal caso possiamo iniziare a scrivere \(L\) come \( S\,(;\,S)^* \) in cui ho scritto la stringa in funzione soltanto di \(S\) e usato poi i soliti operatori delle espressioni regolari per comodità. In altre parole il tuo linguaggio è formato da 1 o più parole del linguaggio determinato da S separate da un punto e virgola. A questo punto è sufficiente fare la stessa cosa per \(S\)
Siccome questa grammatica non è regolare non posso fare più ricorso alle espressioni regolari. Possiamo però pensare di applicare \(m_1\) volte la prima regole, \(n_1\) la seconda, \(m_2\) la prima.. e fermarci quando finalmente scegliamo la terza regola. Abbiamo quindi che possiamo scrivere \(S\) come
\[ L(S) = \Biggl\{ \Bigl( \prod_{i=1}^I \; (wcd)^{m_i}\,b^{n_i} \Bigr)\,s\,e^N \Biggr. \; \Biggl| \; N = \sum_{i=0}^{I} n_i, \; \forall \; i \in \{ 1, \dotsc I \}. \; m_i \geq 0 \land n_i \geq 0 \Biggr\} \]
A questo punto possiamo infilare questa espressione nella precedente e ottenere:
\[ L(G) = \{ s_0\, (;\, s_i)^n \mid n \geq 0, s_0, s_i \in L(S) \} \]
Grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo