Esercizio 1 di linguaggi e traduttori
Salve ragazzi qualkuno può aiutarmi con questo esercizio sulle grammatiche?
Design the grammars for the following languages:
d) the set of all strings of 0s and 1s with an unequal number of 0s and 1s
Complicatuccio...almeno per me
Design the grammars for the following languages:
d) the set of all strings of 0s and 1s with an unequal number of 0s and 1s
Complicatuccio...almeno per me
Risposte
Comincerei da come sei abituato a procedere. Usi un metodo particolare? Costruisci un automa? Vai "a naso"?
Un punto di partenza: sei in grado di costruire una grammatica che genera le stringhe con uguale numero di zeri e uno?
Un punto di partenza: sei in grado di costruire una grammatica che genera le stringhe con uguale numero di zeri e uno?
No l'automa non lo costruisco, in teoria vado a naso, tentando di individuare le proprietà della grammatica.
Quella grammatica che dici si sono in grado di costruirla.
Io pensavo questo
Numero diverso di 0 e 1 implica che #0 < #1 unione #0 > #1 (# è la cardinalità)
da ciò significa che posso costruire il linguaggio come unione di due linguaggi
Il linguaggio in cui il numero di 0 è inferiore al numero di 1 e viceversa.
Ma comunque non riesco a definire una grammatica adeguata.
Quella grammatica che dici si sono in grado di costruirla.
Io pensavo questo
Numero diverso di 0 e 1 implica che #0 < #1 unione #0 > #1 (# è la cardinalità)
da ciò significa che posso costruire il linguaggio come unione di due linguaggi
Il linguaggio in cui il numero di 0 è inferiore al numero di 1 e viceversa.
Ma comunque non riesco a definire una grammatica adeguata.
E' una buona idea. Cominciamo da qui
Io direi
$S-> 0S1S | 1S0S | epsilon$
e prova da questa a trovare la grammatica (ovvero le altre produzioni) per renderla con più caratteri 0 (risp. 1).
"Lauke":
Quella grammatica che dici si sono in grado di costruirla.
Io direi
$S-> 0S1S | 1S0S | epsilon$
e prova da questa a trovare la grammatica (ovvero le altre produzioni) per renderla con più caratteri 0 (risp. 1).
Ho trovato la soluzione, ma confesso che non ci sarei mai arrivato...
Le produzioni sono le seguenti...
$S \rarr A | B $
$A \rarr A A | AE | EA | 1E | E1 $
$B \rarr BB | BE | EB | 0E | E0 $
$E \rarr 0E1E | 1E0E | \epsilon $
Però anche se non lo trovata io sono riuscito a dimostrare che è corretta...diciamo mi accontento. Si basa più o meno sull'idea che avevo in mente, quanto meno per la costruzione, ma a tutte queste produzioni non ci sarei mai arrivato.
Però non ho trovato nulla su quest'altro esercizio... non è che mi potreste un suggerimento su questo?
Design grammars for the following languages
f) The set of all strings of 0s and 1s of the form $ xy $ , where $ x != y $ and $x$ and $y$ are of the same length.
Per questa grammatica sarò ho provato a ragionare come segue
La stringa che devo ottenere è una stringa della forma seguente
$ \omega_{x_p} 0 \omega_{x_s} \omega_{y_p} 1 \omega_{y_s} $ oppure $ \omega_{x_p} 1 \omega_{x_s} \omega_{y_p} 0 \omega_{y_s} $
con le seguenti proprietà
$\{( | \omega_{x_p} | = | \omega_{y_p} | ),(| \omega_{x_s} | = | \omega_{y_s} | ):}
Per cui ho provato a costruire varie grammatiche sperando di trovare una relazione generale diciamo, ad esempio ho provato a costruire la grammatica per la seguente
stringa
$ \omega_{x_p} 0 \omega_{x_s} \omega_{y_p} 1 $
E la grammatica risultante è la seguente
$S \rarr X_s 1 $
$X_s \rarr X_p X_s Y_p | 0 X_0$
$X_0 \rarr 0X_0 | 1 X_0 | \epsilon $
$X_p = 0 | 1 $
$Y_p = 0 | 1 $
che dovrebbe essere corretta, però non riesco a generalizzarla al caso che mi serve...qualche suggerimento su questa sarebbe di grandissimo aiuto.
Le produzioni sono le seguenti...
$S \rarr A | B $
$A \rarr A A | AE | EA | 1E | E1 $
$B \rarr BB | BE | EB | 0E | E0 $
$E \rarr 0E1E | 1E0E | \epsilon $
Però anche se non lo trovata io sono riuscito a dimostrare che è corretta...diciamo mi accontento. Si basa più o meno sull'idea che avevo in mente, quanto meno per la costruzione, ma a tutte queste produzioni non ci sarei mai arrivato.
Però non ho trovato nulla su quest'altro esercizio... non è che mi potreste un suggerimento su questo?
Design grammars for the following languages
f) The set of all strings of 0s and 1s of the form $ xy $ , where $ x != y $ and $x$ and $y$ are of the same length.
Per questa grammatica sarò ho provato a ragionare come segue
La stringa che devo ottenere è una stringa della forma seguente
$ \omega_{x_p} 0 \omega_{x_s} \omega_{y_p} 1 \omega_{y_s} $ oppure $ \omega_{x_p} 1 \omega_{x_s} \omega_{y_p} 0 \omega_{y_s} $
con le seguenti proprietà
$\{( | \omega_{x_p} | = | \omega_{y_p} | ),(| \omega_{x_s} | = | \omega_{y_s} | ):}
Per cui ho provato a costruire varie grammatiche sperando di trovare una relazione generale diciamo, ad esempio ho provato a costruire la grammatica per la seguente
stringa
$ \omega_{x_p} 0 \omega_{x_s} \omega_{y_p} 1 $
E la grammatica risultante è la seguente
$S \rarr X_s 1 $
$X_s \rarr X_p X_s Y_p | 0 X_0$
$X_0 \rarr 0X_0 | 1 X_0 | \epsilon $
$X_p = 0 | 1 $
$Y_p = 0 | 1 $
che dovrebbe essere corretta, però non riesco a generalizzarla al caso che mi serve...qualche suggerimento su questa sarebbe di grandissimo aiuto.
"Lauke":
Ho trovato la soluzione, ma confesso che non ci sarei mai arrivato...
Carenza di autostima?
Comunqe mi sembrava tu ci potessi arrivare, visto che avevi detto che sai come generare la grammatica "intermedia".
"Lauke":
$S \rarr A | B $
$A \rarr A A | AE | EA | 1E | E1 $
$B \rarr BB | BE | EB | 0E | E0 $
$E \rarr 0E1E | 1E0E | \epsilon $
che sarebbe questa; se ci fai caso, l'ultima produzione è la stessa che ho messo io (e che hai detto conoscevi). Insomma, ti mancava solo un piccolo passo.
"Lauke":
f) The set of all strings of 0s and 1s of the form $ xy $ , where $ x != y $ and $x$ and $y$ are of the same length.
Per questa grammatica sarò ho provato a ragionare come segue
La stringa che devo ottenere è una stringa della forma seguente
$ \omega_{x_p} 0 \omega_{x_s} \omega_{y_p} 1 \omega_{y_s} $ oppure $ \omega_{x_p} 1 \omega_{x_s} \omega_{y_p} 0 \omega_{y_s} $
con le seguenti proprietà
$\{( | \omega_{x_p} | = | \omega_{y_p} | ),(| \omega_{x_s} | = | \omega_{y_s} | ):}
Per cui ...
Per cui il ragionamento mi sembra perfetto. Ci ho pensato un po' su e sono arrivato ad un metodo analogo (e credo la soluzione).
La stringa è $xy$ con $x!=y$ pertanto è della forma che hai indicato
$xy= \omega_{x_p} 0 \omega_{x_s} \omega_{y_p} 1 \omega_{y_s} $ oppure $xy= \omega_{x_p} 1 \omega_{x_s} \omega_{y_p} 0 \omega_{y_s} $
Ma se ci fai caso la lunghezza della stringa fra lo 0 e l'1 (o viceversa) è comunque la somma della lunghezza del prefisso e del suffisso, quindi analogamente possiamo dire
$xy= \omega_{x_p} 0 \omega_{y_p} \omega_{x_s} 1 \omega_{y_s} $ oppure $xy= \omega_{x_p} 1 \omega_{y_p} \omega_{x_s} 0 \omega_{y_s} $
quindi il PDA si può costruire, ed è un linguaggio context-free; allora ho pensato a
$S->AB|BA
$A->CAC|0
$B->CBC|1
$C->0|1
Secondo me funziona. Magari verifica e fammi sapere.
Per la grammatica di prima ho provato a dimostrare che fosse corretta, e quella mi è venuta. Per la sua costruzione continuo a dirti era troppo xD.
Per quanto riguarda l'ultimo esercizio non credo che la grammatica proposta da te vada bene e per dimostrarlo considera che la stringa $ 1001 $ appartiene al linguaggio definito dalla tua grammatica, risulta infatti
$ S \rarr AB \rarr CACB \rarr 1ACB \rarr 10CB \rarr 100B \rarr 1001 $
Per cui non credo vada...hai definito un insieme più grande
Per quanto riguarda l'ultimo esercizio non credo che la grammatica proposta da te vada bene e per dimostrarlo considera che la stringa $ 1001 $ appartiene al linguaggio definito dalla tua grammatica, risulta infatti
$ S \rarr AB \rarr CACB \rarr 1ACB \rarr 10CB \rarr 100B \rarr 1001 $
Per cui non credo vada...hai definito un insieme più grande
"Lauke":
Per quanto riguarda l'ultimo esercizio non credo che la grammatica proposta da te vada bene e per dimostrarlo considera che la stringa $ 1001 $ appartiene al linguaggio definito dalla tua grammatica, risulta infatti
$ S \rarr AB \rarr CACB \rarr 1ACB \rarr 10CB \rarr 100B \rarr 1001 $
Ma scusa, la stringa 1001 non è della forma $xy$ con $x!=y$ e $|x|=|y|$? Infatti è $x=10$ e $y=01$... cosa c'è che non va? Forse sono io che non ho capito...
Hai ragione tu...scusami, è corretto. E l'ho dimostrato, ma non riesco a scrivere che ciò che dici è vero sul forum, s'inceppa il sito mentre scrivo.
Comunque ti ringrazio molto, i tuoi suggerimenti, soprattutto per quest'ultimo esercizio, mi hanno aperto la mente.
Alla prossima!!!
Comunque ti ringrazio molto, i tuoi suggerimenti, soprattutto per quest'ultimo esercizio, mi hanno aperto la mente.
Alla prossima!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo