Disegnare un DFA che accetti L = {stringhe in {a, b}* che iniziano e finiscono per 'a'}
Dare un'espressione regolare che rappresenti il linguaggio L.
Soluzione: a(a+b)*a + a
Convertire l'NFA in figura in un DFA.
Con la costruzione per sottoinsiemi si ottiene la seguente tabella.
| 0 | 1 | |
|---|---|---|
| -> p | pq | p |
| pq | pqr | pr |
| pqr | pqrs | pr |
| pr | pqs | p |
| pqrs* | pqrs | prs |
| pqs* | pqrs | prs |
| prs* | pqs | ps |
| ps* | pqs | ps |
Gli stati pqrs e pqs possono essere fatti collassare in un solo stato, visto che sono entrambi finali e hanno le stesse transizioni. Stesso discorso vale per prs e ps.
L'automa deterministico che risulta è il seguente:
L = {anbmcn-m | n > m > 0} è regolare?
Non è regolare. Per dimostrarlo formalmente è sufficiente mostrare che nega il Pumping Lemma.
Sia n la lunghezza data dal Pumping Lemma.
Prendo una parola w (∈ L) nella forma anbmcn-m con n > m > 0.
Scelgo un k ≥ 0 in modo che ∀ split w = x y z:
- |xy| ≤ n
- y ≠ ε
- x yk z ∉ L.
Per le prime due delle 3 condizioni y deve essere composta da almeno una 'a'. Indico questo numero con p. Allora scelgo k = 0 e allora w' = x y0 z = an-pbmcn-m. Questa stringa non può essere in L.
Siccome nega il PL, L non è regolare.
Sia L un linguaggio regolare su un alfabeto Σ. Dimostrare che anche il seguente linguaggio è regolare:
init(L) = {w ∈ Σ* | esiste x ∈ Σ* tale che wx ∈ L}
Questo liguaggio è regolare perchè è possibile costruire un automa che lo accetta. Infatti init(L) è il linguaggio dei prefissi (propri e imporopri) di L. Quindi è sufficiente:
- disegnare l'automa (NFA) M che accetta
L. - disegnare un nuovo automa N, uguale al precedente ma con un nuovo e unico stato finale
f. - da ogni stato di N che in M poteva (con qualunque cammino) raggiungere uno stato finale, inserisco una ε-transizione verso
f.
A questo punto N può accettare tutti i prefissi delle stringhe in L (incluse le stringhe in L stesse). Quindi L(N) = init(L) è regolare.
Data la CFG G:
S => aSb | aSa | bSa | bSb | ε
Rispondere alle seguenti domande.
- Descrivere il linguaggio L generato da G.
- L = {w | w ∈ {a, b}* tale che |w| sia pari}.
- Dimostrare che L=L(G).
w∈ L(G) <=>w∈ L
-
Dimostrazione => Per induzione sul numero di passi di derivazione (
n).CASO BASE:
n = 1 => S => ε. Questa parola ∈ L.
INDUZIONE: (n ≥ 2)
Supponiamo che ogni stringa prodotta in (n-1) passi di derivazione sia anche in L. Allora, per fare
npassi la produzione deve cominciare con:- S => aSb (n-1)=> a x b
- S => aSa (n-1)=> a y a
- S => bSa (n-1)=> b w a
- S => bSb (n-1)=> b z b
In tutti e 4 i casi
x, y, w, zsono prodotte in (n-1) passi e per ipotesi induttiva appartengono ad L. Pertanto aggiungendo una lettera all'inizio e alla fine la stringa generata innpassi sarà sempre di lunghezza pari. Quindi tutte le stringhe ottenute ∈ L. -
Dimostrazione <= Per induzione sulla lunghezza di
w, |w| = n.CASO BASE:
n = 0 ==> w = ε. È generata con S => ε.
INDUZIONE: (n ≥ 2)
Ogni stringa di lunghezza pari è nella forma
w = l x lconl∈ {a, b}. Siccomexdeve essere inL, suppongo per ipotesi induttiva cheS *=> x. Allora posso usare una delle prime quattro produzioni e ottenerew. Infatti:- S => aSa => a x a
- S => aSb => a x b
- S => bSa => b x a
- S => bSb => b x b
Queste sono tutte le possibili stringhe di lunghezza
ncon |x| = (n-2).
Lè un linguaggio regolare. Infatti può essere espresso anche dall'espressione regolare((a+b)(a+b))*. In particolare G è una grammatica lineare, perchè contiene al massimo una variabile nel corpo di ogni produzione.
L = {w ∈ {a, b}* | #a < #b}, ovvero tutte le stringhe con più 'b' che 'a'.
Grammatica:
- E => aEbE | bEaE | ε
- S => EbE | SS
E genera tutte le stringhe con numero di 'a' e 'b' uguale (chiamerò questo linguaggio K). S invece usa E per generare tutte le stringhe in L. Ora va dimostrato per induzione. Partendo da dimostrare E.
TESI: w è generata da E <=> w ha ugual numero di 'a' e 'b' (∈ K)
Per induzione su |w| = n
CASO BASE:
- n = 0 ==> w = ε e c'è la produzione E => ε
- n = 2 ==>
w = ab | bae ci sono le produzioni per generarle.
INDUZIONE: (n > 2, ovvero n ≥ 4)
Se w ha #a = #b allora può essere scritta come:
x ab y= w1x ba y= w2
Per forza in entrambi i casi xy ∈ K. Allora per ipotesi induttiva posso affermare che E *=> xy. Inoltre |xy| ≥ 2, quindi deve essere generata a partire da una delle prime due produzioni. Per come sono fatte le produzioni la produzione finale che genera xy deve essere nella seguente forma: E *=> x E y, ovvero tolgo tutte le variabili E con la produzione E => ε, tranne una.
Allora nei rispettivi casi:
- Uso la prima produzione e ottengo E *=> x E y => x aEbE y =>
x ab y = w1. - Uso la seconda produzione per ottenere E *=> x E y => x bEaE y =>
x ba y = w2.
TESI: w è generata da E ==> w ha ugual numero di 'a' e 'b' (∈ K)
Per induzione sulla lunghezza della derivazione (n).
CASO BASE:
- n = 1 ==> E => ε che ∈ K.
INDUZIONE: (n > 1) Allora bisogna cominciare con la prima o seconda produzione:
- E => aEbE (n)=>
a x b y. - E => bEaE (n)=>
b x a y.
Visto che x e y sono prodotte in n passi applico l'ipotesi induttiva per sostenere che entrambe le stringhe siano in K.
Quindi con un passo di derivazione in più vengono aggiunte una 'a' e una 'b' in tutti e due i casi. Quindi a x b y e b x a y devono appartenere a K.
w ∈ L <=> w è generata da S.
Se w ha più 'b' che 'a' allora è in una delle seguenti forme:
- Se
wha esattamente una 'b' in più è possibile scomporla in:
w = x b yconxey∈ K. È generata conS => EbE => xby.
- Se ha
n≥ 2 lettere 'b' in più rispetto alle 'a' allora può sempre essere spezzata in:
w= x1x2x3...xn, dove ogni sequenza xi ha esattamente una lettera 'b' in più rispetto al numero di 'a'.
Per cui ogni xi del caso 2. rientra nelle stringhe descritte nel caso 1. Ma allora con la produzione S => SS ripetuta (n-1) volte e poi sostituendo ad ogni S la produzione EbE posso generare una concatenazione di qualunque stringa con esattamente una 'b' in più rispetto al numero di 'a'.
Per induzione sul numero di passi di derivazione. Sia n tale numero.
CASO BASE: (n = 2)
- S => EbE => b. Ok, questa stringa ∈ L.
INDUZIONE: (n ≥ 3)
- S => SS (n)=>
x y. - S => EbE (n)=>
x b y.
Nel primo caso suppongo per ipotesi induttiva che x e y ∈ L, visto che sono prodotte in n passi. Allora la loro concatenazione, generata in (n+1) passi, deve essere in L.
Nel secondo caso so già, avendo dimostrato il linguaggio di E, che x, y ∈ K (hanno lo stesso numero di 'a' e 'b'). Allora aggiungendo una 'b' si ottiene una stringa in L.
L = {akblam | m = k + l}
Grammatica:
- S => aSa | B
- B => bBa | ε
Sia K = {w | w = bmam}, il linguaggio delle stringhe prodotte da B.
TESI: w ∈ K => w è generata da B.
Si dimostra per induzione sulla lunghezza di w (|w| = n).
CASO BASE:
- n = 0 ==> w = ε. È generata con B => ε
INDUZIONE: (n ≥ 2)
Ogni stringa in K di lunghezza (n+2) può essere scomposta in: w = b x a, con x ∈ K. Invoco l'ipotesi induttiva su x, visto che |x| = n. Pertanto B *=> x.
Allora con la prima produzione posso ottenere w: B => b B a *=> b x a. Quindi ogni stringa in K può essere prodotta da B.
TESI: w generata da B => w ∈ K.
Per induzione sul numero di passi di derivazione (n).
CASO BASE:
- n = 1 ===> B => ε, la quale è una stringa ∈ K.
INDUZIONE: (n ≥ 2)
Per fare almeno due passi di derivazione è necessario usare la prima produzione:
B => bBa (n-1)=> b x a. Invoco l'ipotesi induttiva per sostenere che x sia in K, in quanto stringa prodotta in (n-1) passi.
Se x = bmam, aggiungendo una 'b' iniziale e una 'a' alla fine ottengo una stringa
w = bm+1am+1, che è sempre in K.
TESI: w ∈ L <=> w generata da S.
Per induzione sulla lunghezza di w, indicata con n.
CASO BASE:
- n = 0 ==> w = ε. È generata con S => B => ε
INDUZIONE: (n ≥ 2)
w = akblal+k.
Se:
- k = 0. Allora per la dimostrazione precedente qualunque stringa nella forma blal è generata con S => B *=>
w. - k ≥ 1. Allora
w = a x a, conx= ak-1blal+k-1. Applico l'ipotesi induttiva suxper sostenere cheS *=> x. A questo punto è facile generarewcon
S => aSa *=> a x a == w.
Per induzione sul numero di passi di derivazione (n).
CASO BASE:
- n = 2 ===> S => B => ε, la quale è una stringa ∈ L.
INDUZIONE: (n ≥ 3) Allora devo iniziare con:
- S => aSa (n)=> a x a.
- S => B (n)=> x.
Nel caso 2, x sarà ∈ L per la dimostrazione fatta di B. Infatti K ⊂ L (K è il linguaggio delle stringhe prodotte da B).
Nel caso 1 invoco l'ipotesi induttiva per sostenere che x ∈ L. Quindi per forza anche a x a avrà il corretto numero di 'a' finali, e quindi anche questa stringa ∈ L.
Scrivere una CFG per L.
L = {w ∈ {a, b, c}* | #a + #b = #c}
S => SaScS | ScSaS | SbScS | ScSbS | ε
w ∈ L <=> w è generata da S.
Si fa per induzione su |w| = n.
CASO BASE:
- |w| = 0. Allora
w= ε. È generata con S => ε
INDUZIONE: (|w| ≥ 2)
Se w ∈ L allora può sempre essere scritta come:
- w1 =
x ac y - w2 =
x ca y - w3 =
x cb y - w4 =
x bc y
Allora xy ∈ L e ovviamente |xy| = n-2 (posto che |w| = n). Allora suppongo, per ipotesi induttiva che S *=> xy. Però, per come sono fatte le produzioni, la produzione che genera xy sarà di questo tipo:
S *=> x S y => xy. Quindi posso fare un passaggio in più e ottenere:
- S *=> x S y => x SaScS y =>
x ac y - S *=> x S y => x ScSaS y =>
x ca y - S *=> x S y => x SbScS y =>
x bc y - S *=> x S y => x ScSbS y =>
x cb y
Cioè usando le 4 produzioni posso generare tutte le stringhe dei 4 casi indicati sopra. Quindi qualunqu stringa ∈ L è generabile da S.
Per induzione sul numero di passi di derivazione (n).
CASO BASE:
- n = 1: è possibile usare solo S => ε. E ε ∈ L.
INDUZIONE: (n ≥ 2) Per fare almeno 2 passi è necessario cominciare con una delle prime 4 produzioni:
- S => SaScS (n-1)=>
x a y c z - S => ScSaS (n-1)=>
x c y a z - S => SbScS (n-1)=>
x b y c z - S => ScSbS (n-1)=>
x c y b z
x, y, z sono tutte prodotte in n-1 passi, quindi uso l'ipotesi induttiva per sostenere che tutte appartengono ad L.
Ma allora anche le stringhe prodotte nei 4 casi avranno il corretto numero di 'a', 'b' e 'c' in quanto, in tutti i casi sto solo aggiungendo una 'c' e un'altra lettera scelta fra 'a' e 'b'.