(Informatica Teorica) linguaggio regolare o no?
salve a tutti! spero tanto che qualcuno possa aiutarmi in questo quesito di informatica teorica.
Parlo di un linguaggio e di capire se è regolare o meno.
L={w $in$ {0,1}* | w contiene un numero non uguale di 0 e 1}
ho provato con il Pumping Lemma, ma trovo che il linguaggio è regolare. nel senso, provo a suddividere una stringa, ma pompando o meno la y (w=x $y^i$ z) risulta sempre che |0| $!=$ |1|
allora per essere regolare ho provato a costruire un DFA(automa a stati finiti deterministico) ma senza successo.
sono in una fase di stallo. qualche suggerimento??
grazie mille anticipatamente!
Parlo di un linguaggio e di capire se è regolare o meno.
L={w $in$ {0,1}* | w contiene un numero non uguale di 0 e 1}
ho provato con il Pumping Lemma, ma trovo che il linguaggio è regolare. nel senso, provo a suddividere una stringa, ma pompando o meno la y (w=x $y^i$ z) risulta sempre che |0| $!=$ |1|
allora per essere regolare ho provato a costruire un DFA(automa a stati finiti deterministico) ma senza successo.
sono in una fase di stallo. qualche suggerimento??
grazie mille anticipatamente!
Risposte
L={w ∈ {0,1}* | w contiene un numero non uguale di 0 e 1}
Innanzitutto noto che essendo che il numero di '0' è diverso dal numero di '1', allora sicuramente ci sarà uno '0' in più perchè {0,1}\( ^*\) non può dare origine a una stringa con più uni che zeri.Quindi lo poso tradurre così:
\( L=\){0w | w={1,0}\(^*\)}
Quindi può essere '0', oppure '010', oppure '01010', eccetera...
Allora applichiamo il pumping lemma:
Noto che sia z una stringa | \(z \in L\), allora z ha cardinalità dispari.
Secondo il pumping lemma esiste una costante \(N > 0\) con \(|z| \ge N\), imoltre per ogni z deve essere possibile suddividere la stringa in tre sottostringhe:
- \(|uv|\le N\);
- \(|v| \ge1\);
-per ogni \(k \ge 0\), \(uv^kw \in L\).
Basta trovare uno e un solo caso che non rispetta queste condizioni e hai dimostrato che il linguaggio non è regolare.Se invece vuoi dimostrare che il linguaggio è regolare dovresti fare tutti i casi (che sono infiniti).Ma il pumping lemma è buono per dimostrare che un linguaggio non è regolare.
Quindi nel caso sia \(z=010\), suddivido z in \(u=01,v=0,w=\epsilon\).
Con k=2, \(uv^2w\)=\(0100\)\(\notin L\).
Se avessi scelto \(u=0,v=10,w=\epsilon\),sarebbe stato con k=2, \(uv^2w=01010 \in L\), ma ciò non avrebbe dimostrato che il linguaggio è egolare.Basta infatti una e una sola contraddizione a quelle tre condizioni e allora ho dimostrato che il linguaggio non è regolare.Si può anche andare per tentativi prendendo stringhe casuali.
Quindi L non è regolare.
"A occhio" puoi notare che un linguaggio è regolare se "pompando" una sua stringa (cioè allungandola o accorciandola ripetendo più volte o cancellando una loro sottostringa ), ottengo ancora una stringa che appartiene al linguaggio.
Se fosse stato \(L=\){(0\(^*\)1\(^*\))\(^*\) }
Allora era regolare e penso si possa vedere " a occhio" perchè posso ad esempio con \(z=01\) prendere la sottostringa 1, espanderla all' infinito e concatenarla a z, ottenendo ancora un linnguaggio che \( \in L\).
Innanzitutto noto che essendo che il numero di '0' è diverso dal numero di '1', allora sicuramente ci sarà uno '0' in più perchè {0,1}\( ^*\) non può dare origine a una stringa con più uni che zeri.Quindi lo poso tradurre così:
\( L=\){0w | w={1,0}\(^*\)}
Quindi può essere '0', oppure '010', oppure '01010', eccetera...
Allora applichiamo il pumping lemma:
Noto che sia z una stringa | \(z \in L\), allora z ha cardinalità dispari.
Secondo il pumping lemma esiste una costante \(N > 0\) con \(|z| \ge N\), imoltre per ogni z deve essere possibile suddividere la stringa in tre sottostringhe:
- \(|uv|\le N\);
- \(|v| \ge1\);
-per ogni \(k \ge 0\), \(uv^kw \in L\).
Basta trovare uno e un solo caso che non rispetta queste condizioni e hai dimostrato che il linguaggio non è regolare.Se invece vuoi dimostrare che il linguaggio è regolare dovresti fare tutti i casi (che sono infiniti).Ma il pumping lemma è buono per dimostrare che un linguaggio non è regolare.
Quindi nel caso sia \(z=010\), suddivido z in \(u=01,v=0,w=\epsilon\).
Con k=2, \(uv^2w\)=\(0100\)\(\notin L\).
Se avessi scelto \(u=0,v=10,w=\epsilon\),sarebbe stato con k=2, \(uv^2w=01010 \in L\), ma ciò non avrebbe dimostrato che il linguaggio è egolare.Basta infatti una e una sola contraddizione a quelle tre condizioni e allora ho dimostrato che il linguaggio non è regolare.Si può anche andare per tentativi prendendo stringhe casuali.
Quindi L non è regolare.
"A occhio" puoi notare che un linguaggio è regolare se "pompando" una sua stringa (cioè allungandola o accorciandola ripetendo più volte o cancellando una loro sottostringa ), ottengo ancora una stringa che appartiene al linguaggio.
Se fosse stato \(L=\){(0\(^*\)1\(^*\))\(^*\) }
Allora era regolare e penso si possa vedere " a occhio" perchè posso ad esempio con \(z=01\) prendere la sottostringa 1, espanderla all' infinito e concatenarla a z, ottenendo ancora un linnguaggio che \( \in L\).
caspita complimenti! più chiaro di così non si poteva!
anche se non è detto che io abbia più 0 che 1, ma anche il contrario!!
ma il discorso non cambia! può essere applicato anche nel caso qui sopra!
più che altro ho pensato che se prendo il mio linguaggio, lo interseco con 0*1*, ottengo il classico $0^n$ $1^n$ che sappiamo non è regolare...
comunque provo a dimostrarlo come dici te!
grazie mille!!
anche se non è detto che io abbia più 0 che 1, ma anche il contrario!!
ma il discorso non cambia! può essere applicato anche nel caso qui sopra!
più che altro ho pensato che se prendo il mio linguaggio, lo interseco con 0*1*, ottengo il classico $0^n$ $1^n$ che sappiamo non è regolare...
comunque provo a dimostrarlo come dici te!
grazie mille!!
no mi correggo:
tutte le condizioni sono verificate col pumping lemma, perché se fosse come dici te il mio linguaggio sarebbe:
L={w $in$ {0,1}* | w=$0^i$ $1^j$, i=j+1} che non è il mio esercizio..
tutte le condizioni sono verificate col pumping lemma, perché se fosse come dici te il mio linguaggio sarebbe:
L={w $in$ {0,1}* | w=$0^i$ $1^j$, i=j+1} che non è il mio esercizio..
Stai facendo confuzione, guarda che :
{0,1}\(^*\) \( \ne\) \(0^*1^*\)
{0,1}\(^*\) può essere una stringa che contiene k volte '01', ma 000111 \( \notin\) {0,1}\(^*\), deve essere una ripetzione (anche nulla) di '01', quindi se contiene 3 zeri e 3 uni può essere solo '010101'.
Non può mai essere '01010', ecco perchè ho modificato il linguaggio.
Non esiste un linguaggio L={w\(\in\){0,1}\(^*\)} tale che w contenga un numero di uni diverso dal numero di zeri, ecco perchè l' ho modificato.Come dici te si poteva anche modificare in modo tale che il numero di uni fosse superiore al numero di zeri.
Il pumping lemma applicato a quel linguaggio dimostra che non è regolare perchè ad esempio \(0100 \notin L\).
Hai preso \(010 \in L\), ha preso la sottostringa \(v=0\) e l' hai "allungata" replicando 0,ottenendo una stringa che non appartiene al linguaggio;Quindi è un linguaggio non regolare.
{0,1}\(^*\) \( \ne\) \(0^*1^*\)
{0,1}\(^*\) può essere una stringa che contiene k volte '01', ma 000111 \( \notin\) {0,1}\(^*\), deve essere una ripetzione (anche nulla) di '01', quindi se contiene 3 zeri e 3 uni può essere solo '010101'.
Non può mai essere '01010', ecco perchè ho modificato il linguaggio.
Non esiste un linguaggio L={w\(\in\){0,1}\(^*\)} tale che w contenga un numero di uni diverso dal numero di zeri, ecco perchè l' ho modificato.Come dici te si poteva anche modificare in modo tale che il numero di uni fosse superiore al numero di zeri.
Il pumping lemma applicato a quel linguaggio dimostra che non è regolare perchè ad esempio \(0100 \notin L\).
Hai preso \(010 \in L\), ha preso la sottostringa \(v=0\) e l' hai "allungata" replicando 0,ottenendo una stringa che non appartiene al linguaggio;Quindi è un linguaggio non regolare.
"ramy1989":
{0,1}\(^*\) può essere una stringa che contiene k volte '01', ma 000111 \( \notin\) {0,1}\(^*\)
Nel mio mondo ${0,1}^star$ significa "stringhe binarie (eventualmente vuote)". Quindi
$'01' in {0,1}^star$
$'10' in {0,1}^star$
$'000111' in {0,1}^star$
Non ho mai visto considerare i simboli ordinati, se non usando gli apici ($'01'^star$) o le parentesi tonde ($(01)^star$), e sempre senza la virgola.
Che notazione (secondo me bizzarra) state usando, e chi ve l'ha spiegata così?
beh w$in$ {0,1}* sono tutte quelle stringhe appartenenti a tale alfabeto!
il linguaggio l'ho spiegato prima:
in parole: w non contiene lo stesso numero di 0 e di 1
in simboli $0^i$$1^j$ tale che i $!=$j
quindi sono tutte stringhe del tipo 001 00111 0001111
ma anche 011 0111111111111111111111 e 0000111111111111111
Quindi, o è regolare per il pumping lemma, oppure per la regola di intersezione
non lo è... e sinceramente a questo punto non lo so neanche io!!!
il linguaggio l'ho spiegato prima:
in parole: w non contiene lo stesso numero di 0 e di 1
in simboli $0^i$$1^j$ tale che i $!=$j
quindi sono tutte stringhe del tipo 001 00111 0001111
ma anche 011 0111111111111111111111 e 0000111111111111111
Quindi, o è regolare per il pumping lemma, oppure per la regola di intersezione
se prendo il mio linguaggio, lo interseco con 0*1*, ottengo il classico $0^n$ $1^n$ che sappiamo non è regolare...
non lo è... e sinceramente a questo punto non lo so neanche io!!!
"m3c4":
beh w$in$ {0,1}* sono tutte quelle stringhe appartenenti a tale alfabeto!
Appunto. L'alfabeto è $Sigma={0,1}$ quindi $L=Sigma^star={0,1}^star$ è il linguaggio delle stringhe binarie. Di TUTTE le stringhe formate da caratteri '0' e '1', inclusa la stringa vuota.
"m3c4":
in simboli $0^i$$1^j$ tale che i $!=$j
No, questo è un linguaggio differente che è solo un sottoinsieme di $L$ come definito sopra.
Guarda che {0,1}\(^*\) non può essere 01111
E' una ripetizione di '01', non può nemmeno essere '10'.
Se tu intendevi chiedere se il linguaggio L={w* | w=0\(^*\)1\(^*\)}
Che può cioè essere '00011111' oppure '010101011', eccetera ...
Allora si che è regolare e lo vedo a occhio perchè ogni stringa z se è composta da simboli che sono o '0' o '1', allora \(z\in L\) in ogni caso, e ad ogni modo non sono in grado di trovare una violazione delle condizioni del pumping lemma.
Ad esempio z='001100', applico il pumping lemma:
|z|=6
Fisso \(u=00\), \(v=11\) e \(w=00\)
Per k=3, \(uv^3w \in L\) perchè \(uv^3w\) = 0011111100 \( \in L\)
E in nessun altro caso viola le condizioni del pumping lemma, ma lo si può anche intuire dal fatto che una qualsiasi stringa, purchè abbia simboli che appartengono all' alfabeto {0,1}, appartiene a L.
E' una ripetizione di '01', non può nemmeno essere '10'.
Se tu intendevi chiedere se il linguaggio L={w* | w=0\(^*\)1\(^*\)}
Che può cioè essere '00011111' oppure '010101011', eccetera ...
Allora si che è regolare e lo vedo a occhio perchè ogni stringa z se è composta da simboli che sono o '0' o '1', allora \(z\in L\) in ogni caso, e ad ogni modo non sono in grado di trovare una violazione delle condizioni del pumping lemma.
Ad esempio z='001100', applico il pumping lemma:
|z|=6
Fisso \(u=00\), \(v=11\) e \(w=00\)
Per k=3, \(uv^3w \in L\) perchè \(uv^3w\) = 0011111100 \( \in L\)
E in nessun altro caso viola le condizioni del pumping lemma, ma lo si può anche intuire dal fatto che una qualsiasi stringa, purchè abbia simboli che appartengono all' alfabeto {0,1}, appartiene a L.
"ramy1989":
Guarda che {0,1}\(^*\) non può essere 01111
Sbagli. ${0,1}^\star $ è l'insieme di tutte le stringhe formate da $0$ e $1$.
$(01)^\star$ è l'insieme di tutte le stringhe formate dalla concatenazione di zero o più stringhe del tipo $01$.
Non ho voglia di scrivere la dimostrazione con il pumping lemma, ma il linguaggio ad occhio non dovrebbe essere regolare: gli automi a stati finiti non sanno contare, non sono in grado di affermare se una parola contiene lo stesso numero di $0$ e $1$.
Cmq la dimostrazione non è difficile: prendi il complemento del linguaggio e prova a dimostrarne la non regolarità; è la stessa identica dimostrazione che $a^nb^n$ non è regolare.
Non ho capito, quindi {0,1}\(^*\) può essere 0001111, ma potrebbe anche essere 01010101 ?
"ramy1989":
Non ho capito, quindi {0,1}\(^*\) può essere 0001111, ma potrebbe anche essere 01010101 ?
Sì, certo.
E come ha detto anche Deckard, il linguaggio non è regolare. La dimostrazione non è difficile: oltre alla soluzione da lui proposta, si può fare anche per distinzione di casi, sempre usando il pumping lemma (è praticamente equivalente).
Ma ogni stringa che contiene uni e zeri \(\in L\), come si fa a contraddire il pumping lemma?
"ramy1989":
Ma ogni stringa che contiene uni e zeri $in L$, come si fa a contraddire il pumping lemma?
"m3c4":
L={w $in$ {0,1}* | w contiene un numero non uguale di 0 e 1}
Supponiamo sia z=010
Applico il pumping lemma, |z|=3 , stabilisco che u=0 , v=1 , w=0.
Allora con k=2, uv\(^2\)w = 0110 \(\notin L\) perchè non contiene un numero uguale di uni e di zeri.
Se non c'era la restrizione che il numero di zeri e di uni doveva essere diverso, allora L era regolare.
Applico il pumping lemma, |z|=3 , stabilisco che u=0 , v=1 , w=0.
Allora con k=2, uv\(^2\)w = 0110 \(\notin L\) perchè non contiene un numero uguale di uni e di zeri.
Se non c'era la restrizione che il numero di zeri e di uni doveva essere diverso, allora L era regolare.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo