[Informatica Teorica]Non regolarità di un linguaggio
Dimostrare che $ L={a^lb^m m>l} $ non è un linguaggio regolare.
Mi aiutato ad applicare passo passo il pumping lemma?Trovo molte difficoltà
Mi aiutato ad applicare passo passo il pumping lemma?Trovo molte difficoltà
Risposte
Ciao ElCastigador 
Prima appunto di passare a degli esempi bisogna aver chiaro a cosa serve il pumping lemma. Sostanzialmente è un lemma, appunto, che fornisce una condizione necessaria ma non sufficiente per affermare che un certo linguaggio appartiene ad una determinata classe. In virtù di questo lo si può usare solitamente per affermare che un linguaggio non appartiene a tale classe. E' largamente usato ad esempio per affermare che un linguaggio non è regolare (ma ne esiste una versione anche per i linguaggi liberi da contesto).
Ora, senza star qui a riscrivere inutilmente tutto l'enunciato del pumping lemma, intuitivamente possiamo affermare che un linguaggio è regolare se per ogni stringa $z$ del nostro linguaggio riusciamo a determinare $n \in \mathbb{N}$ tale per cui ogni suddivisione $uvw$ della nostra stringa $z$ tale che $|uv| \le n$ e $|v| \ge 1$, la stringa $uv^iw \quad (i \ge 0)$ fa ancora parte del nostro linguaggio.
Per mostrare che il linguaggio da te proposto non è regolare possiamo dunque vedere se tale condizione "cade". Supponiamo dunque di avere una generica stringa del nostro linguaggio $z = a^l b^m$ con $m > l$ di lunghezza $n$ (ossia $n = l + m$). Vediamo quindi se, in base alla composizione di $v$, possiamo pensare di "pompare" tale stringa ottenendo ancora stringhe del nostro linguaggio:
Prima appunto di passare a degli esempi bisogna aver chiaro a cosa serve il pumping lemma. Sostanzialmente è un lemma, appunto, che fornisce una condizione necessaria ma non sufficiente per affermare che un certo linguaggio appartiene ad una determinata classe. In virtù di questo lo si può usare solitamente per affermare che un linguaggio non appartiene a tale classe. E' largamente usato ad esempio per affermare che un linguaggio non è regolare (ma ne esiste una versione anche per i linguaggi liberi da contesto).
Ora, senza star qui a riscrivere inutilmente tutto l'enunciato del pumping lemma, intuitivamente possiamo affermare che un linguaggio è regolare se per ogni stringa $z$ del nostro linguaggio riusciamo a determinare $n \in \mathbb{N}$ tale per cui ogni suddivisione $uvw$ della nostra stringa $z$ tale che $|uv| \le n$ e $|v| \ge 1$, la stringa $uv^iw \quad (i \ge 0)$ fa ancora parte del nostro linguaggio.
Per mostrare che il linguaggio da te proposto non è regolare possiamo dunque vedere se tale condizione "cade". Supponiamo dunque di avere una generica stringa del nostro linguaggio $z = a^l b^m$ con $m > l$ di lunghezza $n$ (ossia $n = l + m$). Vediamo quindi se, in base alla composizione di $v$, possiamo pensare di "pompare" tale stringa ottenendo ancora stringhe del nostro linguaggio:
[*:1yazua8e]Se $v$ è composta da sole $a$ allora "pompando" questa otterremo prima o poi stringhe con un numero di $a$ maggiore $b$. Ne deriva dunque che $l > m$ e pertanto questa composizione di $v$ è da scartare;[/*:m:1yazua8e]
[*:1yazua8e]Se $v$ è composta da sole $b$ allora saremmo tentati di pensare che non vi sia alcun problema poiché "pompando" $v$ otteniamo delle stringhe in cui la condizione $m > l$ continua a valere. Tuttavia questa suddivisone non permette di generare tutte le stringhe del linguaggio ed è anche'essa da scartare. Infatti se ad esempio $u = \epsilon$ (stringa vuota) allora pompando $v = b$ si generano stringhe di sole $b$ e se $u = a$ allora deve essere $v = b.b.b^\star$ (i puntini in mezzo alla formula non c'entrano, li ho messi solo perché altrimenti il generatore di formule mi dà errore). Analogamente si ragiona con $u = aaa^\star$. E' evidente però che questi casi "limitano" il nostro linguaggio permettendo di generare solo determinate stringhe e tralasciandone altre;[/*:m:1yazua8e]
[*:1yazua8e]Se $v$ è composta sia da $a$ che da $b$ "pompando" questa risulta evidente come le stringhe generate non rispettino più la forma delle parole del nostro linguaggio ($a$ e $b$ ripetutamente alternate).[/*:m:1yazua8e][/list:u:1yazua8e]
Concludendo, poiché le condizioni sulla composizione di $v$ sono violate non vale il pumping lemma per questo linguaggio e pertanto lo stesso non è regolare.
Non mi è chiaro benissimo il punto 2 che è il motivo per cui ho postato la domanda.Perchè pompi due b minimo con la terza stellata e lo stesso per a?
Riporto la dimostrazione che avevo fatto io,cosi mi dici se è corretta.
Per assurdo L regolare.Esisite un DFA che lo riconosce con n stati.
Considero la stringa appartenente al linguaggio x= $ a^nb^(n+1) $ in modo da rispettare l'ipotesi del Pumping Lemma
Per il Pumping Lemma x=uvw con v>0,v può essere fatta in 3 modi:
CASO 1) v= $ a^z $ con z>0.Per il pumping lemma anche y=uvvw deve appartenere al linguaggio,ma ciò è assurdo in quanto otteniamo più a che b.
CASO 2) v= $ b^z $ con z>0.Per il pumping lemma anche y=uw deve appartenere al linguaggio( $ v^0 $ ),ma ciò è assurdo perchè stiamo eliminando dalla stringa almeno una b e,per come era fatta x,otteniamo minimo un numero di a uguale al numero di b,per cui ciò è assurdo.
CASO3) v= $ a^zb^k $ z,k>0.Per il pumping lemma anche y=uvvw deve appertenere al linguaggio,ma ciò è assurdo in quanto perdiamo l'ordine di sole a seguite da sole b(si ottiene una cosa del tipo aaaabababbbbbbb)
Riporto la dimostrazione che avevo fatto io,cosi mi dici se è corretta.
Per assurdo L regolare.Esisite un DFA che lo riconosce con n stati.
Considero la stringa appartenente al linguaggio x= $ a^nb^(n+1) $ in modo da rispettare l'ipotesi del Pumping Lemma
Per il Pumping Lemma x=uvw con v>0,v può essere fatta in 3 modi:
CASO 1) v= $ a^z $ con z>0.Per il pumping lemma anche y=uvvw deve appartenere al linguaggio,ma ciò è assurdo in quanto otteniamo più a che b.
CASO 2) v= $ b^z $ con z>0.Per il pumping lemma anche y=uw deve appartenere al linguaggio( $ v^0 $ ),ma ciò è assurdo perchè stiamo eliminando dalla stringa almeno una b e,per come era fatta x,otteniamo minimo un numero di a uguale al numero di b,per cui ciò è assurdo.
CASO3) v= $ a^zb^k $ z,k>0.Per il pumping lemma anche y=uvvw deve appertenere al linguaggio,ma ciò è assurdo in quanto perdiamo l'ordine di sole a seguite da sole b(si ottiene una cosa del tipo aaaabababbbbbbb)
"ElCastigador":
Non mi è chiaro benissimo il punto 2 che è il motivo per cui ho postato la domanda.Perchè pompi due b minimo con la terza stellata e lo stesso per a?
[...]
Nessun problema, dubbio più che legittimo. Vedo di andare con ordine in modo da farti comprendere.
Allora, in realtà non è vero che che "pompo" $a$, semplicemente considero due casi distinti delle possibili composizioni della stringa $u$, l'ho semplicemente descritta mediante espressione regolare per utilizzare una notazione più compatta, tutto qui. La stringa $u$ infatti non è quella che va "pompata", $v$ invece lo è.
Veniamo pertanto alla $v$ composta a partire dalla sola $b$. Se suppongo $u = \epsilon$ e $v$ come composta da una sola lettera $b$, "pompando" la mia $v$ otterrei delle stringhe di sole $b$ che però non sono le uniche appartenenti al linguaggio e pertanto effettuerei erroneamente una riduzione delle stringhe che posso generare. Se suppongo invece $u = a$ o, più in generale, $u$ come composta da una o più $a$, allora (sempre pensando di costruire $v$ con le sole $b$) $v$ deve essere composta da un numero di $b$ pari almeno dal numero delle $a$ presenti in $u$ più uno (per rispettare la condizione $m > l$). Se ora "pompiamo" la nostra $v$ risulta evidente come anche in tal caso le stringhe che possiamo ottenere non sono tutte quelle generabili col nostro linguaggio.
"ElCastigador":
[...]
Riporto la dimostrazione che avevo fatto io,cosi mi dici se è corretta.
Per assurdo L regolare.Esisite un DFA che lo riconosce con n stati.
Considero la stringa appartenente al linguaggio x= $ a^nb^(n+1) $ in modo da rispettare l'ipotesi del Pumping Lemma
Per il Pumping Lemma x=uvw con v>0,v può essere fatta in 3 modi:
CASO 1) v= $ a^z $ con z>0.Per il pumping lemma anche y=uvvw deve appartenere al linguaggio,ma ciò è assurdo in quanto otteniamo più a che b.
CASO 2) v= $ b^z $ con z>0.Per il pumping lemma anche y=uw deve appartenere al linguaggio( $ v^0 $ ),ma ciò è assurdo perchè stiamo eliminando dalla stringa almeno una b e,per come era fatta x,otteniamo minimo un numero di a uguale al numero di b,per cui ciò è assurdo.
CASO3) v= $ a^zb^k $ z,k>0.Per il pumping lemma anche y=uvvw deve appertenere al linguaggio,ma ciò è assurdo in quanto perdiamo l'ordine di sole a seguite da sole b(si ottiene una cosa del tipo aaaabababbbbbbb)
Non ho capito molto il caso due ma credo che il vero errore sia di porre all'inizio $x = a^n b^{n + 1}$ come stringa di riferimento. Una stringa siffatta non permette infatti di generare tutte le possibili stringhe del nostro linguaggio, che hanno invece un'altra forma. E' un po' come se facessimo erroneamente una restrizione a priori.
Ma non ho bisogno di generare tutte le stringhe del linguaggio.Basta una stringa particolare che appartiene al linguaggio ma che violi il Pumping Lemma per concludere che linguaggio non è regolare.O sbaglio?
Sì, ne basta anche una ma devi sempre e comunque partire da una stringa che appartiene al linguaggio e che poi va "pompata" nella parte centrale, costituita dalla stringa $v$ nel nostro caso. Se però si può partire da una stringa generica che denota le parole generate dal nostro linguaggio tanto meglio, non vedo perché sceglierne una particolare.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo