Definire un DPDA per il linguaggio L che accetti per stack vuoto. Poi convertirlo in DPDA che accetta per stato finale.
L = {anbn | n ≥ 1} ∪ {anc2n | n ≥ 1}
Visto che L gode della proprietà del prefisso è possibile accettarlo con un DPDA anche per pila vuota.
Accettazione per pila vuota:
Conversione in DPDA che accetta per stato finale:
Cioè è sufficiente spostare le transizioni che svuotano lo stack sulle transizioni verso lo stato finale accettante.
L'esercizio T1 del tutorato 7 è deterministico?
No, infatti esistono le due transizioni:
- δ(q1, b, A) = {(q1, ε)}
- δ(q1, ε, A) = {(q1, ε)}
PDA P che accetta palindromi pari. È deterministico?
La definizione di P è la seguente:
P = ({q, p, f}, {0, 1}, {0, 1, Z}, δ, q, Z, {f})
Transizioni:
- δ(q, 0, Z) = {(q, 0Z)}
- δ(q, 1, Z) = {(q, 1Z)}
- δ(q, 0, 0) = {(q, 00)}
- δ(q, 0, 1) = {(q, 01)}
- δ(q, 1, 0) = {(q, 10)}
- δ(q, 1, 1) = {(q, 11)}
- δ(q, ε, Z) = {(p, Z)}
- δ(q, ε, 0) = {(p, 0)}
- δ(q, ε, 1) = {(p, 1)}
- δ(p, 0, 0) = {(p, ε)}
- δ(p, 1, 1) = {(p, ε)}
- δ(p, 0, 0) = {(p, ε)}
- δ(p, ε, Z) = {(f, Z)}
Un automa a pila è deterministico se, ∀ q, a, X valgono questi punti:
- δ(q, a, X) contiene una sola coppia;
- se δ(q, a, X) contiene una coppia, allora δ(q, ε, X) deve essere vuoto.
Quindi l'automa P non è deterministico. Ad esempio le transizioni 2 e 7, 3 e 8 violano la seconda proprietà.
D'altronde questo linguaggio non ha la proprietà del prefisso, quindi non potrebbe essere accettato da un DPDA.
PDA P = ({p, q}, {0, 1}, {X, Z}, δ, q, Z) con le transizioni:
- δ(q, 1, Z) = {(q, XZ)}
- δ(q, 1, X) = {(q, XX)}
- δ(q, 0, X) = {(p, X)}
- δ(q, ε, X) = {(q, ε)}
- δ(p, 1, X) = {(p, ε)}
- δ(p, 0, Z) = {(q, Z)}
In questo caso le transizioni 3 e 4 violano la seconda regola. Quindi P è un automa a pila non deterministico.
Definire DPDA per il linguaggio L = {0n1m, n ≤ m}
Definire DPDA per il linguaggio L = {0n1m, n ≥ m}
Nessuno dei due linguaggi degli ultimi due esercizi ha la proprietà del prefisso, quindi non potrebbero essere accettati da DPDA che accettano per stack vuoto.
Definire DPDA per il linguaggio L = {0n1m0n, con n, m arbitrari}
P = ({q0, q1, q2, q3, q4, q5}, {0, 1}, {Z, 0}, δ, q0, Z, {q0, q4, q5})
Alcuni casi limite:
- 02n è accettata, in quanto le transizioni fra
q0eq1servono proprio ad assicurarsi che la stringa si soli '0' sia di lunghezza pari. - Anche 1m è accettato. Infatti se
q2vede unaZsullo stack, vuol dire che non sono stati letti '0' prima degli '1', e quindi transita inq5che accetta qualunque numero di '1'. - La stringa vuota è accettata da
q0.
Trasformare la CFG:
- eliminare le ε-produzioni;
- eliminare produzioni unitarie;
- eliminare simgoli inutili (non generatori e non raggiungibili);
- mettere in forma normale di Chomsky.
CFG:
- S => ASB | ε
- A => aAS | a
- B => SbS | A | bb
I simboli annullabili sono: Z = {S}
Sostituiamo ogni simbolo annullabile (in questo caso solo S) con la possibilità che ci sia, oppure no:
- S => ASB | AB
- A => aAS | aA | a
- B => SbS | Sb | bS | b | A | bb
Le coppie unitarie sono:
- (S, S) => \
- (A, A) => \
- (B, B) => (B, A)
Quindi ottengo:
- S => ASB | AB
- A => aAS | aA | a
- B => SbS | Sb | bS | b | bb | aAS | aA | a
- Sia S, A, B sono generatori;
- Inoltre sono anche tutti raggiungibili.
Tutte le produzioni devono essere costituite da 2 variabili oppure da un terminale.
- S => AE | AB
- A => MF | MA | a
- B => GS | SN | NS | b | MF | MA | a | NN
- M => a
- N => b
- E => SB
- F => AS
- G => SN
Trasformare la CFG:
- eliminare le ε-produzioni;
- eliminare produzioni unitarie;
- eliminare simgoli inutili (non generatori e non raggiungibili);
- mettere in forma normale di Chomsky.
- S => 0A0 | 1B1 | BB
- A => C
- B => S | A
- C => S | ε
I simboli annullabili sono: Z = {C, A, B, S}
- S => 0A0 | 00 | 1B1 | 11 | BB | B
- A => C
- B => S | A
- C => S
Questa grammatica accetta lo stesso linguaggio di quella originle, a meno del simbolo ε (dato che S era annullabile).
Le coppie unitarie sono:
- (S, S) => (S, B), (S, A), (S, C)
- (A, A) => (A, C), (A, S), (A, B)
- (B, B) => (B, S), (B, A), (B, C)
- (C, C) => (C, S), (C, B), (C, A)
Quindi la grammatica diventa:
- S => 0A0 | 00 | 1B1 | 11 | BB
- A => 0A0 | 00 | 1B1 | 11 | BB
- B => 0A0 | 00 | 1B1 | 11 | BB
- C => 0A0 | 00 | 1B1 | 11 | BB
I generatori sono: π = {0, 1, S, A, B, C}. I raggiungibili sono: R = {S, A, 0, 1, B}.
Quindi C va rimossa perchè non raggiungibile, ma in realtà si possono rimuovere anche A e B perchè sono identiche ad S.
Quindi rimane:
- S => 0S0 | 00 | 1S1 | 11 | SS
- S => XE | EE | YF | FF | SS
- X => ES
- Y => FS
- E => 0
- F => 1
- S => AAA | B
- A => aA | B
- B => ε
I simboli annullabili sono: Z = {B, S, A}.
Siccome B può produrre solo la stringa vuota, va rimossa, e di conseguenza va tolta anche ogni produzione che contiene B nel corpo.
Quindi:
- S => AAA | AA | A
- A => aA | a
Il linuaggio di questa grammatica è identico al precedente tranne per la stringa vuota che non è più possibile produrre.
Coppie unitarie:
- (S, S) => (S, A)
- (A, A) => \
Quindi:
- S => AAA | AA | aA | a
- A => aA | a
I generatori sono π = {a, A, S}. I raggiungibili sono R = {S, A, a}. Quindi non cambia nulla.
Devono restare solo produzioni con un terminale oppure due variabili nel corpo.
- S => BA | AA | CA | a
- A => CA | a
- B => AA
- C => a
Scrivere una grammatica CNF per le stringhe di parentesi bilanciate.
Una possibile grammatica non normalizzata é:
- S => (S) | SS | ()
Che in CNF diventa:
- S => AC | SS | BC
- A => BS
- B => (
- C => )
- S => XY
- X => abb | aXb | ε
- Y => c | cY
Solo la variabile X è annullabile.
- S => XY | Y
- X => abb | aXb | ab
- Y => c | cY
Coppie unitarie:
- (S, S) => (S, Y)
- (X, X) => \
- (Y, Y) => \
Quindi basta aggiungere ad S le produzioni non unitarie di Y:
- S => XY | c | cY
- X => abb | aXb | ab
- Y => c | cY
Sono tutti generatori, e sono tutti raggiungibili.
- S => XY | c | CY
- X => AD | AE | AB
- Y => c | CY
- C => c
- A => a
- B => b
- D => BB
- E => XB
Descrivere le ID della TM in figura 8.10 (del libro) con la parola in input 000111.
[q0]000111 -| X[q1]00111 -| X0[q1]0111 -| X00[q2]111 -| X0[q2]0Y11 -| X[q2]00Y11 -| [q2]X00Y11 -| X[q0]00Y11 -| ... riparte dall'inizio ...
TM che accetta L = {anbncn | n ≥ 1}.
NB: il simbolo blank si indica con '□' in JFLAP.
M = ({q0, q1, q2, q3, q4, q5}, {a, b, c}, {X, Y, □}, δ, q0, □, {q5})
TM che accetta L = {wwR | w è una qualunque stringa di 0 e 1}
(palindromi pari).
N = ({q0, q1, q2, q3, q4, q5, q6}, {0, 1}, {X, □}, δ, q0, □, {q6})
