Automa a pila che accetta stringhe in {a, b}* che NON sono nella forma ww, ovvero non sono formate da una stringa ripetuta.
È utile evidenziare una proprietà di tutte le stringhe che sono nella forma ww.
- Sia
wuna qualunque stringa in formaw = xx. Queste stringhe devono essere di lunghezza pari e quindi sia|w| = 2t. Chiamo xi il simbolo in posizioneidella stringax. Allora xi+t = xi, ∀itale che 1 ≤i≤ t (considerando che l'indice del primo simbolo sia 1).
Allora deve essere anche vero che una stringa che non sia nel formato ww deve avere almeno una coppia per cui non valga questa proprietà, ovvero una coppia xi+t ≠ xi
L'automa quindi si assicurerà di accettare solamente stringhe per le quali esista almeno una di tali coppie.
P = ({q0, q1, q2, q3, q4, q5, q6, q7}, {a, b}, {Z, X}, δ, q0, Z, {q7})
Disegno dell'automa P che accetta per stato finale:
L'automa legge un numero k di simboli. Poi, nondeterministicamente sceglie la xi. In seguito legge altri k simboli e poi altri l. Quando trova un simbolo diverso da xi, prova a considerarlo come elemento xi+t. Se poi legge esattamente l simboli allora accetta, altrimenti questo ramo 'morirà'.
Le stringhe dispari sono sempre accettate perchè un match sempre valido è xi+t = ε
Data la seguente grammatica libera da contesto G:
- S => aB
- B => Ab | b
- A => aB | a
Rispondere alle seguenti domande: a. Dare una definizione del linguaggio di G; b. Dimostrare induttivamente che G produce tutte e sole le stringhe del linguaggio; c. Descrivere un automa pila che riconosca L(G) per stato finale e spiegare perché secondo voi funziona.
I primi due punti sono già stati svolti nell'esercizio T1 del Tutorato 4.
L(G) = {w | w = anbm con n = m oppure n = m+1 con n e m > 0}
Quindi un automa a pila che accetta L(G) è definito:
P = ({q0, q1, q2, q3}, {a, b}, {A, Z}, δ, q0, Z, {q2})
Le transizioni di P sono le seguenti:
Funzionamento:
- con gli stati
q0eq1semplicemente fa match delle 'a' con le 'b' rimuovendo una 'A' dallo stack per ogni 'b' che legge; - con
q3prova a togliere una 'A' dallo stack senza leggere input. Se dopo averla tolta vede la 'Z' (il fondo), allora vuol dire che c'è esattamente una 'a' in più rispetto alle 'b'. Quindi la stringa appartiene a L(G) ePla accetta, andando nello stato finale (cason = m+1); - in alternativa, con la transizione fra
q1eq2accetta quando le 'b' inserite hanno consumato tutte le 'A' sulla pila (cason = m); - per arrivare nello stato
q1,Pdeve leggere almeno una 'a' seguita da una 'b'. Quindi è garantito chen > 0em > 0.
Convertire la grammatica G in PDA.
- S => aAA
- A => aS | bS | a
Quindi in G:
- V = {S, A}
- T = {a, b}
L'automa costruito sarà:
N = ({q}, T, T ∪ V, δ, q, S)
E le sue transizioni sono:
- δ(q, ε, S) = {(q, aAA)}
- δ(q, ε, A) = {(q, aS), (q, bS), (q, a)}
- δ(q, a, a) = {(q, ε)}
- δ(q, b, b) = {(q, ε)}
Definire una CFG per L = {aibjck | i = 2j oppure j = 2k, i, j, k ≥ 0} e convertire in PDA.
La grammatica G ha le seguenti produzioni:
- S => TC | AP
- A => aA | ε
- C => cC | ε
- T => aaTb | ε
- P => bbPc | ε
Ora bisogna dimostrare che una stringa w ∈ L <=> w è prodotta da G.
Ometto la dimostrazione per A e C che sono molto semplici. Infatti produzono semplicemente un qualunque numero di 'a' e 'c'.
Dimostrerò invece che T genera L(T) = {aibj | i = 2j, con i, j ≥ 0}
e P genera L(P) = {bjck | j = 2k, con j, k ≥ 0}
Si fa per induzione sulla lunghezza delle stringhe. Per entrambe le grammatiche le stringhe avranno una lunghezza multipla di 3.
CASO BASE:
- |w| = 0 =>
w= ε. È prodotta in entrambi i casi.
INDUZIONE: |w| ≥ 3
Una stringa w rispettivamente in L(T) e L(P) dovrà avere la seguente forma:
- aa
xb =w1. Allorax∈L(T) - bb
yc =w2. Alloray∈L(P)
Allora essendo x e y stringhe di lunghezza |w|-3 e visto che per forza entrambe devono appartenere ai rispettivi linguaggi, posso supporre che siano prodotte dalle rispettive variabili della grammatica. Ovvero, per ipotesi induttiva:
T *=> xP *=> y
Allora è possibile utilizzare la prima produzione e generare le stringhe iniziali:
- T => aaTb *=>
aa x b=w1 - P => bbPc *=>
bb y c=w2
Si fa per induzione sul numero di passi di derivazione.
CASO BASE:
n = 1passo. AlloraTePpossono produrre solo ε che è in entrambi i linguaggi.
INDUZIONE: n ≥ 2 passi
Allora w1 e w2 sono prodotte con la prima produzione:
- T => aaTb (n-1)=>
aa x b - P => bbPc (n-1)=>
bb y c
Suppongo per ipotesi induttiva che tutte le stringhe prodotte in n-1 passi siano appartenenti ai rispettivi linguaggi (L(T) e L(P)). Allora nei due casi precedenti, se y e x appartengono ai linguaggi, anche aa x b e bb y c dovranno farlo. Infatti sto solo aggiungendo due lettere prima e una dopo, come richiede il linguaggio.
Quindi l'ipotesi è corretta.
A questo punto è immediato vedere che S => TC | AP produce tutte e sole le stringhe in L.
Una volta dimostrata che la grammatica è corretta è semplice trovare un PDA che accetti per pila vuota lo stesso linguaggio.
NB: Nel disegno la variabile S è stata sostituita con Z, perche JFLAP vuole Z come simbolo iniziale di stack.
N = ({q}, {a, b, c}, {Z, T, C, A, P, a, b, c}, δ, q, Z);
- Costruire un automa a pila che accetti L = {anbn, ∀ n ≥ 1}
- Convertire l'automa in grammatica libera dal contesto
Per comodità riporto tutte le transizioni:
- δ(p, a, Z) = {(p, AZ)}
- δ(p, a, A) = {(p, AA)}
- δ(p, b, A) = {(q, ε)}
- δ(q, b, A) = {(q, ε)}
- δ(q, ε, Z) = {(r, ε)}
Produzioni della grammatica:
- Tutti i modi di togliere il simbolo
Zdallo stato inizialep- S => [pZp] | [pZq] | [pZr]
- Dalla produzione 1 (rimuovo
AZpartendo dap):- [pZp] => a[pAp][pZp] | a[pAq][qZp] | a[pAr][rZp]
- [pZq] => a[pAp][pZq] | a[pAq][qZq] | a[pAr][rZq]
- [pZr] => a[pAp][pZr] | a[pAq][qZr] | a[pAr][rZr]
- Dalla produzione 2 (rimuovo
AApartendo dap, 32 produzioni):- [pAp] => a[pAp][pAp] | a[pAq][qAp] | a[pAr][rAp]
- [pAq] => a[pAp][pAq] | a[pAq][qAq] | a[pAr][rAq]
- [pAr] => a[pAp][pAr] | a[pAq][qAr] | a[pAr][rAr]
- Dalla produzione 3:
- [pAq] => b
- Dalla produzione 4:
- [qAq] => b
- Dalla produzione 5:
- [qZr] => ε
Un PDA è così definito: P = ({q, p}, {a, b}, {a, Z}, δ, q, Z, {q}) dove δ è come segue:
- δ(q, a, Z) = {(q, aZ)}
- δ(q, a, a) = {(q, aa)}
- δ(q, b, a) = {(q, ε)}
- δ(q, b, Z) = {(p, ε)}
Rispondere alle domande:
- Descrivere il linguaggio riconosciuto da P.
- Trasformare P in PDA che accetta per pila vuota lo stesso linguaggio.
- Determinare una grammatica libera dal contesto che accetti lo stesso linguaggio di P.
Disegno del PDA:
L'automa accumula 'a' nella pila, e ne consuma una ogni volta che viene letta una 'b'. Quando viene inserita una 'b' in più rispetto al numero di 'a' finora letto, l'automa transita nello stato p dove muore.
Quindi L(P) = {w ∈ {a, b}* | ogni prefisso di w abbia #a ≥ #b}
Lo stato finale di P dovrà avere una transizione che indipendentemente da cosa sia sulla pila, deve svuotarla.
Secondo la regola è necessario aggiungere un simbolo (diverso da {a, Z}) che funga da nuovo simbolo iniziale, per garantire che lo stack non possa svuotarsi in uno stato non finale di P, provocando l'accettazione di una stringa non in L(P). E in effetti è necessaria, altrimenti la transizione verso lo stato p svuoterebbe lo stack.
PDA risultante V = ({q, p, i, r}, {a, b}, {a, Z, X}, δ, i, X):
NB: in JFLAP il simbolo di stack iniziale è sempre Z. Per questo, invece che partire con X e mettere Z, nel disegno l'automa parte con Z e mette subito X come fondo (perchè non si può scegliere X come simbolo iniziale). La transizione corretta, con X simbolo iniziale, sarebbe: δ(i, ε, X) = {(q, ZX)}.
Per agevolare la procedura di 'conversione' di P in grammatica l'automa V può essere ulteriormente semplificato fino ad avere un unico stato (non deterministico):
Le transizioni di V semplificato sono:
- δ(q, a, Z) = {(q, aZ)}
- δ(q, a, a) = {(q, aa)}
- δ(q, b, a) = {(q, ε)}
- δ(q, ε, Z) = {(q, ε)}
- δ(q, ε, a) = {(q, ε)}
Quindi le produzioni della CFG corrispondente sono:
- Tutti i modi di togliere
Zdallo stato inizialeq- S => [qZq]
- Dalla transizione 1:
- [qZq] => a[qaq][qZq]
- Dalla transizione 2:
- [qaq] => a[qaq][qaq]
- Dalla transizione 3:
- [qaq] => b
- Dalla transizione 4:
- [qZq] => ε
- Dalla transizione 5:
- [qaq] => ε