Esercizio linguaggi formali

[bekert]

Ciao a tutti, sto iniziando lo studio del corso Automi e linguaggi formali, e dopo poche pagine di lettura scorrevole si è presentato un esercizio che mi risulta essere difficile da comprendere e svolgere

considerate il linguaggio L = {w ∈ {0, 1}^∗ | w ha più 0 che 1}.
Prendete a scelta una w ∈ L e considerate il linguaggio
pref (wL) = {x | x è un prefisso di w}. Il linguaggio pref (wL) gode
della stessa proprietà di L?

Sapreste darmi una mano? Grazie

[Pompolus]

Ciao a tutti, sto iniziando lo studio del corso Automi e linguaggi formali, e dopo poche pagine di lettura scorrevole si è presentato un esercizio che mi risulta essere difficile da comprendere e svolgere

considerate il linguaggio L = {w ∈ {0, 1}^∗ | w ha più 0 che 1}.
Prendete a scelta una w ∈ L e considerate il linguaggio
pref (wL) = {x | x è un prefisso di w}. Il linguaggio pref (wL) gode
della stessa proprietà di L?

Sapreste darmi una mano? Grazie

non ricordo esattamente tutte le proprietà dei linguaggi comuqnue a prima vista direi che la risposta è no.

w è una qualsiasi parola formata da qualsiasi combinazione di 0 e 1 purchè abbia più 0 che 1.
Prendendo come esempio w=1110000 e w'= 100, una possibile parola di pref(WL), prendendo come prefisso 111, potrebbe essere 1111000, che non rispetterebbe la proprietà di avere più 0 che 1.

Prendilo con le molle però

[bekert]

non ricordo esattamente tutte le proprietà dei linguaggi comuqnue a prima vista direi che la risposta è no.

w è una qualsiasi parola formata da qualsiasi combinazione di 0 e 1 purchè abbia più 0 che 1.
Prendendo come esempio w=1110000 e w'= 100, una possibile parola di pref(WL), prendendo come prefisso 111, potrebbe essere 1111000, che non rispetterebbe la proprietà di avere più 0 che 1.

Prendilo con le molle però


Grazie mille seguendo il tuo ragionamento ora è più chiaro

[Pompolus]

Grazie mille seguendo il tuo ragionamento ora è più chiaro

prego, son contento che finalmente l'esame di linguaggi sia servito a qualcosa :D