a\L = {w ∈ Σ* | aw ∈ L}
Dimostrare che se L è regolare anche a\L è regolare.
Si dimostra effettuando una serie di operazioni che mantengono la regolarità.
- Se L è regolare possiamo disegnare un DFA
Mche accetta L. - Possiamo 'invertire' l'automa modificandolo per accettare LR, ovvero tutte le stringhe di L ma rovesciate. Questo automa si chiama
M'= (QM', Σ, δM', q0, FM'). - Disegno il DFA
M''che è uguale aM'ma ha come stati finali solamente gli stati diM'che hanno una transizione conaverso uno stato finale.M''= (QM'', Σ, δM'', q0, FM'').
- ∀ q ∈ QM'
- δM'(q, a) = p ∈ FM' <==> q ∈ FM''
M''accetta stringhe wR sseM'accetta wRa. Ovvero il linguaggio diM''è L(M'') = {wR | wRa ∈ LR}.
- Inverto
M''creandoM'''che accetta lewtali che a(wR)R ∈ (LR)R, ovvero lewtali cheaw∈L.
M''' accetta quindi il linguaggio iniziale che è regolare.
substring(L) = {w | ∃ x, y | xwy ∈ L}.
Dimostrare che se L è regolare allora anche substring(L) è regolare.
Si parte dall'automa che accetta L. Dato che L è regolare disegno l'automa NFA che lo accetta e lo chiamo M = (Q, Σ, δ, q0, F).
Sia S l'insieme degli stati raggiungibili da q0 con qualunque cammino, anche ε. Sia E l'insieme degli stati che possono raggiungere uno stato finale di M, ovvero almeno uno stato ∈ F.
Disegno un nuovo automa che è uguale a M, ma ha un nuovo stato iniziale qi, e un nuovo (unico) stato finale qf. Costruisco l'NFA:
N = (Q ∪ {qi, qf}, Σ, δ, qi, {qf})
Inoltre:
- qi avrà delle ε-transizioni verso qualunque stato ∈
S. - tutti gli stati ∈
Eavranno una ε-transizione verso qf.
In questo modo N accetta esattamente il linguaggio substring(L), che quindi è regolare.
NB: ε = λ;
Possibile soluzione: ((λ+aa(aa)*)ab)*(a+aa(aa)*(λ+a))
Soluzione: (b+abb*a)*a
Dimostrare che L non è regolare.
L = {w ∈ {0, 1}* | ∃u | www = uu}
Se fosse regolare rispetterebbe PL.
∀ lunghezza h prendo la parola w = 10h110h1.
Essendo w due volte una stessa sequenza (r = s = 10h1, w = rs = ss = rr), www sarà spezzabile in due stringhe identiche che concatenate ricostruiscono www. Quindi w ∈ L.
∀ possibile split w = xyz con |xy| ≤ h e y ≠ ε allora prendo k = 0 e la stringa w' = xy0z sarà necessariamente in una forma in cui non è più la ripetizione di due sequenze identiche. Diciamo che è nella forma w = rs in cui |r| < |s| ed esse non sono uguali.
Quindi www = rsrsrs. Non c'è alcun modo di spezzare questa stringa in due pezzi identici, quindi w' ∉ L. Segue che L non può essere regolare.
L è regolare?
L = {0m1n | m = n}
Verifico che nega il PL.
∀ lunghezza h prendo la parola w = 0h1h+h! (∈ L, |w| ≥ h).
∀ possibile split w = xyz con |xy| ≤ h e y ≠ ε. Allora y è formata da p zeri, con 1 ≤ p ≤ h.
Prendo k = 1 + (h! / p).
Allora w' = xykz = 0h-p 0p(1 + (h! / p)) 1h+h! = 0h-p 0(p + h!) 1h+h! = 0h-p 0p 0h! 1h+h! = 0h+h! 1h+h!.
Per cui w' ∉ L. ==> L non è regolare.
Il fattoriale serve perchè k deve essere un intero. h! / p è intero perchè p ≤ h e quindi h! è sicuramente divisibile per p.
L = {0n | n è un numero composto (non primo)}
Per dimostrarne l'irregolarità si può utilizzare la proprietà di chiusura per complementazione dei linguaggi regolari. Se fosse regolare allora il suo complementare L' = {0n | n è un numero primo} dovrebbe essere regolare. Ma questo non è regolare, il che porta ad una contraddizione. Quindi L non è regolare.
Dimostro che L non è regolare.
L = {0n | n è un cubo perfetto}
Sia n la lunghezza del PL.
Prendo w = 0n3, che è sicuramente un cubo ∀ n e |w| ≥ n.
∀ split w = xyz per cui vale:
- |xy| ≤
n; y≠ ε
Allora y contiene p zeri, dove 1 ≤ p ≤ n.
Prendo un k = 2. Sia w' = xykz.
Dunque |w'| = n3-p + 2p = n3+p.
Quindi ripetto a w la parola w' avrà al più n zeri in più. Sono sufficienti per arrivare ad un cubo perfetto?
Il cubo successivo a n3 è (n+1)3.
(n+1)3 = n3 + 3n2 + 2n + 2.
Quindi sarebbe stato necessario incrementare il numero di zeri di 3n2+2n+2 solo per arrivare al cubo successivo, invece w' è cresciuta di al più n zeri.
Quindi w' ∉ L.
Costruire un DFA che accetta tutte le stringhe che lette al contrario come un numero binario intero siano divisibili per 5.
Per prima cosa basta disegnare il DFA che accetta i multipli di 5 binari (diritti). Poi è sufficiente invertire l'automa con la procedura usuale e si ottiene il DFA richiesto.
