|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.IT-LinguaggiNonRegolari History
Hide minor edits - Show changes to output
Changed line 27 from:
# per ogni i>=0, xy'^i^'z ⊆ A to:
# per ogni i>=0, xy'^i^'z ∈ A Changed lines 34-35 from:
Il teorema del ''pumping lemma'' dice che tutti i linguaggi regolari godono di una certa proprietà, che se verificata in un linguaggio L ne certifica la regolarità. La proprietà è questa: qualunque stringa di L deve poter essere divisa in tre parti, chiamate ''x'' ''y'' e ''z'', tali che la stringa xy'^n^'z (ottenuta replicando, o meglio, pompando ''n'' volte l'elemento centrale) appartenga ancora ad L. In altre parole, ogni stringa di L deve contenere una sottostringa che può essere ripetuta un qualunque numero di volte. to:
Il teorema del ''pumping lemma'' dice che tutti i linguaggi regolari godono di una certa proprietà, che se verificata in un linguaggio L ne certifica la regolarità. La proprietà è questa: qualunque stringa di L deve poter essere divisa in tre parti, chiamate ''x'' ''y'' e ''z'', tali che la stringa xy'^n^'z (ottenuta replicando, o restando in tema, pompando ''n'' volte l'elemento centrale) appartenga ancora ad L. In altre parole, ogni stringa di L deve contenere una sottostringa che possa essere ripetuta un qualunque numero di volte. Deleted lines 37-40:
Infine per quanto riguarda la condizione 3, dobbiamo assicurarci che q'_9_' è la prima ripetizione della sequenza. Ma per il principio che abbiamo enunciato prima, il primo stato p+1 nella sequenza deve per forza contenere una ripetizione, quindi |xy|<=p.
Changed lines 48-49 from:
Premettendo che gli indici degli stati nell'esempio sono del tutto casuali, possiamo affermare che: q'_1_' è lo stato iniziale, q'_3_' è lo stato che si ripete, q'_6_' è quello finale su cui M accetta. to:
Premettendo che gli indici degli stati nell'esempio sono del tutto casuali, possiamo affermare che in questo caso: q'_1_' è lo stato iniziale, q'_3_' è lo stato che si ripete, q'_6_' è quello finale su cui M accetta. Changed lines 51-54 from:
# x = s'_1_'...s'_j-1_'
# y = s'_j_'...s'_l-1_'
# z = s'_l_'...s'_n_'
to:
* x = s'_1_'...s'_j-1_'
* y = s'_j_'...s'_l-1_'
* z = s'_l_'...s'_n_' Changed lines 63-64 from:
Ovvero, non ci interessa quante volte si ripete il ciclo su q'_3_', tanto comunque poi ci sposteremo (attraversando ''z'') verso lo stato finale. to:
Ovvero, non ci interessa quante volte si ripete il ciclo su q'_3_', tanto poi comunque ci sposteremo (attraversando ''z'') verso lo stato finale. Changed lines 71-72 from:
Ora che siamo freschi di teoria, usiamo la strategia del ''pumping lemma'' per dimostrare che il linguaggio B dell'Esempio 1 è non regolare. La dimostrazione si fa per contraddizione, ovvero si assume che B è regolare e poi si dimostra che si giunge a contraddizioni. to:
Ora che siamo freschi di teoria, usiamo la strategia del ''pumping lemma'' per dimostrare che il linguaggio B dell'Esempio 1 è non regolare. La dimostrazione si fa per contraddizione, ovvero si assume che B sia regolare e poi si dimostra che ciò porta a contraddizioni. Changed line 75 from:
Ok, assumiamo che B sia regolare e diciamo che ''p'' è il pumping length.\\
to:
Assumiamo che B sia regolare e diciamo che ''p'' è il pumping length.\\ Changed line 80 from:
# la sottostringa ''y'' è formata di 0 e di 1. In questo caso un'eventuale stringa xyyz avrebbe sì lo stesso numero di 0 e di 1, ma non si rispetta più il formato secondo cui tutti gli 0 precedono gli 1. Nada, anche in questo caso la nuova stringa non è più in B. to:
# la sottostringa ''y'' è formata di 0 e di 1. In questo caso un'eventuale stringa xyyz avrebbe sì lo stesso numero di 0 e di 1, ma non rispetterebbe più il formato secondo cui tutti gli 0 precedono gli 1. Nada, anche in questo caso la nuova stringa non è più in B.
Added lines 1-90:
(:title Informatica Teorica - Linguaggi non regolari :)
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
----
%titolo%''':: Informatica Teorica - Linguaggi non regolari ::'''
%center% %sottotitolo% Appunti & Dimostrazioni del 17 Marzo
!!Esempio 1 - linguaggio non regolare
Supponiamo di dover realizzare un automa a stati finiti [@n.d.@] che riconosca il seguente linguaggio:\\
''B = {0'^n^'1'^n^' | n>=0}''
Il compito dell'automa sembra semplice, capire se la stringa in ingresso ha lo stesso numero di 0 e di 1. Il problema è che il numero ''n'' di occorrenze è limitato solo inferiormente, ma non superiormente. Ci ritroviamo per cui nelle condizioni di dover affrontare un numero illimitato di possibilità con un numero finito di stati.\\
Dal momento che non riusciamo a definire un automa a stati finiti che lo riconosca, possiamo affermare che il linguaggio B è non regolare.
Ocio però: non possiamo basarci solo sulla quantità di memoria (quindi di stati) richiesta per distinguere tra linguaggi regolari e non. Ci sono infatti molti casi che ''apparentemente'' prevedono un numero illimitato di possibilità, ma in realtà sono regolari. Ad esempio il linguaggio:\\
''D = {w | w ha un ugual numero di occorrenze di 01 e 10 come sottostringhe}''
Sembra analogo al linguaggio B, ma in realtà è regolare. Fidatevi!\\
Come facciamo allora a distinguere tra linguaggi regolari e non regolari? Ovvio, con le solite affascinanti prove matematiche!
!!Pumping lemma
''Pumping lemma'' non è solo il nome del mio criceto, ma anche quello del teorema che permette di provare la (non) regolarità dei linguaggi.
>>left bgcolor=#f5f9fc width=auto border='2px solid #cccccc' padding=5px<<
Se A è un linguaggio regolare, allora esiste un numero ''p'' (chiamato ''pumping length'') tale che se ''s'' è una qualunque stringa in A di lunghezza almeno ''p'', allora ''s'' può essere divisa in tre parti, s=xyz, che soddisfino le seguenti tre condizioni:
# per ogni i>=0, xy'^i^'z ⊆ A
# |y|>0
#|xy|<=''p''
>><<
'''Spiegazione'''
Il teorema del ''pumping lemma'' dice che tutti i linguaggi regolari godono di una certa proprietà, che se verificata in un linguaggio L ne certifica la regolarità. La proprietà è questa: qualunque stringa di L deve poter essere divisa in tre parti, chiamate ''x'' ''y'' e ''z'', tali che la stringa xy'^n^'z (ottenuta replicando, o meglio, pompando ''n'' volte l'elemento centrale) appartenga ancora ad L. In altre parole, ogni stringa di L deve contenere una sottostringa che può essere ripetuta un qualunque numero di volte.
'''Dimostrazione'''
Infine per quanto riguarda la condizione 3, dobbiamo assicurarci che q'_9_' è la prima ripetizione della sequenza. Ma per il principio che abbiamo enunciato prima, il primo stato p+1 nella sequenza deve per forza contenere una ripetizione, quindi |xy|<=p.
Sia M=(''Q'',''Σ'',''δ'',''q'_1_''',''F'') un DFA che riconosca il linguaggio A, e sia ''p'' il numero di stati di M.\\
Sia s=s'_1_'s'_2_'..s'_n_' una stringa in A di lunghezza ''n'', dove ''n>=p''.
Sia infine r'_1_', ... , r'_n+1_' la sequenza di stati che M assume durante la computazione di s, tale che r'_i+1_'=δ(r'_i_',s'_i_') per 1<=''i''<=''n''. Adesso seguitemi bene:
* se la lunghezza della stringa è ''n'', allora il numero di stati che M attraversa è ''n+1'';
* il numero di stati di M è ''p'', e come abbiamo già detto ''n>=p'';
* ma se ''n>=p'', allora sicuramente ''n+1>p'', quindi la sequenza di stati deve avere una ripetizione!
Probabilmente si capisce meglio con un esempio:
%center%Attach:IT-pumpLem1.gif
Premettendo che gli indici degli stati nell'esempio sono del tutto casuali, possiamo affermare che: q'_1_' è lo stato iniziale, q'_3_' è lo stato che si ripete, q'_6_' è quello finale su cui M accetta.
Se chiamiamo il primo degli stati che si ripetono r'_j_' e il secondo r'_l_', possiamo suddividere la stringa in ingresso in questo modo:
# x = s'_1_'...s'_j-1_'
# y = s'_j_'...s'_l-1_'
# z = s'_l_'...s'_n_'
Riprendendo l'esempio avremo:
%center%Attach:IT-pumpLem2.gif
Dato che la sottostringa ''x'' tiene occupato M dallo stato r'_1_' ad r'_j_', la sottostringa ''y'' lo tiene occupato da r'_j_' ad r'_j_', e la sottostringa ''z'' da r'_j_' ad r'_n+1_', che è lo stato accettante, allora M deve accettare xy'^i^'z per qualsiasi i>=0 (''prima condizione del teorema''). Se dovessimo infatti rappresentare il tutto con uno pseudo-automa (in cui le frecce curve tratteggiate permettono di ignorare gli stati intermedi) avremo qualcosa del genere:
%center%Attach:IT-pumpLem3.gif
Ovvero, non ci interessa quante volte si ripete il ciclo su q'_3_', tanto comunque poi ci sposteremo (attraversando ''z'') verso lo stato finale.
Verifichiamo invece la ''seconda condizione del teorema'' osservando che poiché ''j≠l'', allora per forza di cose |y|>0, perché nel peggiore dei casi (tra gli stati che si ripetono non ce ne sono altri) |y| è pari a 1.\\
Infine, dato che tra i primi ''p+1'' elementi della sequenza di stati deve esserci almeno una ripetizione, ovvero ''l<=p+1'', allora |xy|<=p (''terza condizione del teorema'').
Ecco dunque dimostrato il teorema del ''pumping lemma'' per il riconoscimento dei linguaggi regolari.
!!Pumping Lemma su Esempio 1
Ora che siamo freschi di teoria, usiamo la strategia del ''pumping lemma'' per dimostrare che il linguaggio B dell'Esempio 1 è non regolare. La dimostrazione si fa per contraddizione, ovvero si assume che B è regolare e poi si dimostra che si giunge a contraddizioni.
Il linguaggio B diceva: ''B = {0'^n^'1'^n^' | n>=0}''
Ok, assumiamo che B sia regolare e diciamo che ''p'' è il pumping length.\\
Definiamo ''s'' una stringa del tipo 0'^p^'1'^p^'. Dato che ''s'' è in B e che la sua lunghezza è maggiore di ''p'', il teorema del pumping lemma ci garantisce che ''s'' può essere diviso in tre parti ''s=xyz'', dove per ogni i>=0 la stringa ''xy'^i^'z'' è ancora in B.\\
Consideriamo tre possibili casi:
# la sottostringa ''y'' è composta di soli 0. Ma allora ad esempio la stringa xyyz avrebbe uno 0 in più rispetti agli 1, quindi non sarebbe più in B, violando la prima condizione del pumping lemma;
# la sottostringa ''y'' è composta di soli 1. Stesso discorso, ma con gli 1 che superano il numero di 0 violando le condizioni del teorema;
# la sottostringa ''y'' è formata di 0 e di 1. In questo caso un'eventuale stringa xyyz avrebbe sì lo stesso numero di 0 e di 1, ma non si rispetta più il formato secondo cui tutti gli 0 precedono gli 1. Nada, anche in questo caso la nuova stringa non è più in B.
Tutti e tre i casi ci portano a una contraddizione, quindi B non è regolare.
----
[[Torna alla pagina di Informatica Teorica-> Informatica Teorica]]
|
|
