Sfida: RE per tutte le stringhe che interpretate come numeri binari rappresentano un multiplo di 3.
Possibile soluzione: ((0+11)+10(1+00)*01)*
Oppure equivalentemente: (0 + 1(01*0)*1)*
DFA corrispondente:
L'automa modella i possibili resti (modulo 3) di ogni stringa binaria interpretata come numero binario. Pertanto accetta solamente se il resto è 0, cioè quando è un multiplo di 3.
Convertire (0+1)*1(0+1) in ε-NFA.
NFA (semplificato)
Scrivere un’espressione regolare per rappresentare il linguaggio sull’alfabeto {a, b, c} che contiene:
- tutte le stringhe che iniziano con
ae sono composte solo diaoppureb; - la stringa
c;
Soluzione: a(a+b)*+c
Convertire l'esercizio 6.2 in ε-NFA.
Applicando le regole si ottiene una cosa di questo tipo:
Semplificando un po' di ε-transizioni si ottiene questo automa equivalente:
Espressione regolare per tutte le stringhe binarie che cominciano e finiscono per 1.
Soluzione: 1(0+1)*1+1
Scrivere una espressione regolare per le stringhe binarie che contengono almeno tre 1 consecutivi.
Soluzione: (0+1)*111(0+1)*
Scrivere una espressione regolare per le stringhe binarie che contengono almeno tre 1, anche non consecutivi.
Soluzione: 0*1(0+1)*1(0+1)*10*
Oppure: (0+1)*10*10*1(0+1)*
Scrivere una espressione regolare per stringhe di testo che descriva le date in formato GG/MM/AAAA.
Per comodità definisco delle RE per ciascun componente:
- g =
(0(1+2+...+9) + (1+2)(0+1+...+9) + 3(0+1))(esclude00,32+) - m =
0(1+2+...+9) + 1(0+1+2)(esclude00e13+) - a =
(0+1+...+9)(0+1+...+9)(0+1+...+9)(0+1+...+9)
Soluzione: g/m/a (concateno le tre RE inserendo / in mezzo)
Convertire gli automi in RE, procedendo con l'eliminazione degli stati.
Soluzione: (1+0((0+10*1)1)*(0+10*1)0)*
Soluzione: (bb*ab+(a+bb*aa)b*a)*(bb*a+(a+bb*aa)b*)
Dimostrare che L = {0p | 'p' è una potenza di 2} non è regolare.
Prendo una qualunque stringa w ∈ L tale che:
- w = xyz
- |w| ≥ n, ∀ n ≥ 0
- y ≠ ε
- |xy| ≤ n
Siccome w appartiene al linguaggio, allora |w| = |x| + |y| + |z| = p con p potenza di 2.
Per provare che questo linguaggio non è regolare bisogna trovare un k che 'pompando' y faccia uscire la parola dal linguaggio.
Scelgo k = |x| + |z|. Ora 'pompo' la stringa e ottengo w'=xykz;
Ragionando sulla lunghezza di w' risulta che:
|w'| = |x| + |z| + |y|*k = |x| + |z| + |y|*(|x| + |z|) = (|x|+|z|)(|y|+1)
Visto che |x| + |y| + |z| = p è una potenza di due (quindi pari), sono possibili due casi:
|y|è pari ==>|x|+|z|è pari, altrimentipnon sarebbe pari e nemmeno una potenza di 2- ==>
|y|+1è dispari e il prodotto di un numero pari per un numero dispari non può dare una potenza di 2.
- ==>
|y|è dispari ==>|x|+|z|è dispari- ==>
|y|+1è pari e quindi comunque non posso ottenere una potenza di 2
- ==>
Pertanto con questa scelta di k la stringa w' ∉ L.
E quindi, siccome falsifica il PL allora L non può essere regolare.
Provare che L è o non è regolare.
L = {w ∈ {a, b}* | numero di a è pari, il numero di b è dispari}
Sia n la lunghezza del PL.
Per dimostrare che non è regolare devo trovare una w ∈ L con |w| ≥ n tale che:
- y ≠ ε
- |xy| ≤ n
- ∃
kper cui xykz ∉ L
Non è possibile trovare una parola che esca dal linguaggio con qualunque split di w in xyz. Infatti nel caso y contenga un numero pari di a e di b non riusciremo mai a ottenere una parola w' che esca dal linguaggio.
E infatti questo linguaggio è regolare, pertanto rispetta il Pumping Lemma.
Provare che L non è regolare.
L = {w ∈ {a, b}* | il numero di a è maggiore del numero di b}
Supponendo che L sia regolare prendiamo la parola w = an+1bn.
Essa appartiene ad L.
Sia n la lunghezza minima della parola (∀ n ≥ 0).
Sia xyz un qualsiasi split tale che:
- y ≠ ε
- |xy| ≤ n
Allora y conterrà solamente lettere a, in particolare ne avrà almeno una.
Quindi scelgo k = 0 e ottengo una stringa
w'=xy0z. Questa stringa avrà un numero di a ≤ n e pertanto w' ∉ L.
Il linguaggio L = {13n+2 | n ≥ 0} è regolare?
Rappresenta il linguaggio delle stringhe di '1' di lunghezza pari ad un multiplo di 3, + 2.
È regolare perchè è accettato dall'espressione regolare (111)*11.
Il linguaggio L = {0n1m0n | m + n > 0} è regolare?
No, e per dimostrarlo si può mostrare che esso nega il Pumping Lemma.
∀ h ≥ 0 (lunghezza del PL), considero la parola w = 0h1h0h.
w ∈ L e sicuramente h è ≥ 1.
∀ split xyz tale che y ≠ ε e |xy| ≤ h allora y conterrà un numero di 1 pari a p con 1 ≤ p ≤ h.
Allora w' = xy0z = 0h-p1h0h
Dato che (h-p) < h w' ∉ L. Quindi L falsifica il PL.
Il linguaggio L = {w ∈ {a, b}* | numero di a è due volte il numero di b} è regolare?
Non è regolare.
Sia h la lunghezza data dal Pumping Lemma.
Prendo la parola w = bha2h ∈ L.
∀ split xyz di w tale che y ≠ ε e |xy| ≤ h
y conterrà un numero di 'b' che chiamo p con 1 ≤ p ≤ h.
Allora scelgo k = 0 e considero w' = xy0z.
w' sarà nella forma bh-pa2h.
Visto che 2(h-p) < 2h w' ∉ L. Quindi L falsifica il PL e non è regolare.
Dimostrare se L è regolare o meno.
L = {parole nella forma aibjcn | i + j = n, ∀ i,j,n >= 0}
Dimostro che falsifica il PL, che dimostra che L non è regolare.
∀ h bisogna trovare una parola w ∈ L, con |w| >= h t.c.
∀ split w = xyz con |xy| <= h e y ≠ ε
si possa trovare un k t.c. xykz ∉ L.
Considero w = ahbhc2h che ∈ L.
Visto |xy| <= h per forza y conterrà solo lettere a (almeno una).
Basta scegliere un qualunque k ≠ 1 e w' = xykz non potrà appartenere al linguaggio.
Per esempio con k = 2 il numero complessivo di a, diciamo i', sarà sicuramente maggiore di h, e quindi non può essere vero che i' + h = 2h.
Segue che L falsifica il PL e quindi non è regolare.
L = {0n1m0nm | n*m ≠ 0}
L è regolare?
Supponendo che lo sia, allora dovrebbe rispettare il PL ∀ parola.
∀ h >= 0, considero w = 0h1m0hm.
Considero qualunque split in xyz t.c. y ≠ ε e |xy| ≤ h. Quindi y deve essere formata da uno o più 0, ovvero y = 0p, con p > 0.
Allora w'= xy0z è nella forma 0h-p1m0hm, e allora w' ∉ L. Questo perché (h-p)*m < hm. Questo linguaggio falsifica il PL, quindi non è regolare.