Recognize VS Decide

Cosa significa Turing-recognizable

Una macchina di Turing che accetta o no un linguaggio.

In una TM recognizable i possibili esiti sono solo: accetta; rifiuta/loop.

Cosa significa Turing-decidibile

Cosa significa decisore

No, non significa questo

Un decisore è una macchina di Turing che termina sicuramente in uno stato accept o reject e non ha mai loop infiniti.

Perché un decisore nondeterministico accetti un linguaggio, bisogna che almeno uno dei branch termini con uno stato accettato; viceversa perché sia rifiutato bisogna che tutti i branch finiscano in uno stato rifiutato.

 

Teorema 3.16

(in nero la traduzione del Sipser; in blu gli elementi aggiunti da me)

Ogni macchina di Turing nondeterministica ha una macchina di Turing deterministica equivalente.

Idea

Possiamo simulare ogni macchina nondeterministica N con una macchina deterministica D. L'idea sottostante la simulazione è che D provi ogni possibile ramo della computazione nondeterministica di N. Se D trova uno stato accettato in uno dei rami, D accetta, altrimenti la simulazione di D non termina.

Vediamo la computazione di N di un input w come un albero. Ogni ramo di questo ramo rappresenta uno dei rami del nondeterminismo. Ogni nodo del ramo è una configurazione di N. La radice dell'albero è la configurazione di partenza. La TM D cerca in questo albero qualche configurazione accettata. Condurre questa ricerca con attenzione è cruciale, altrimenti si rischia che D non riesca a visitare l'intero albero. Una tentazione - sbagliata - sarebbe quella di fare una ricerca usando l'algoritmo depth-first. Il depth-fist va a fondo di ogni ramo prima di tornare a esplorarne un altro. Se D esplora l'albero in questa maniera, D potrebbe proseguire per sempre giù per uno dei rami e mancare una configurazione accettabile in uno degli altri rami. Così disegnamo D per splorare l'albero usando la ricerca breadth-first. Questa strategia esplora tutti i rami alla stessa profondità prima di proseguire a esplorare un ramo alla profondità successiva. Questo metodo garantisce che D visiterà ogni nodo nell'albero finché non incontrerà una configurazione accettata.

Prova

Simuliamo una macchina deterministica D con tre nastri. Per il teorema 3.13 questa impostazione è equivalente a una a nastro singolo. La macchina D usa i suoi tre nastri in un modo particolare, come illustrato nella seguente figura. Il nastro 1 contiene sempre la stringa di input e non è mai modificato. Il nastro 2 mantiene una copia del nastro di N in ogni ramo della computazione nondeterministica. Il nastro 3 mantiene traccia della locazione di D nell'albero computazionale nondeterministico di N.

Figura 3.17: La TM deterministica D simula la TM nondeterministica N

Consideriamo per prima cosa i dati rappresentati nel nastro 3. Ogni nodo nell'albero può avere al massimo b figli, dove b è la dimensione dell'insieme più largo di scelte date dalla funzione di transizione di N. Per ogni nodo nell'albero assegnamo un indirizzo che è una stringa nell'alfabeto Σb = {1, 2, ..., b}. Assegnamo l'indirizzo 231 al nodo a cui arriviamo iniziando dalla radice, andando dentro il suo secondo figlio, poi dentro il terzo, poi dentro il primo. Ogni simbolo nella stringa ci dice quale schelta fare al prissimo passaggio, quando simuliamo un passo nin un ramo della computazione nondeterministica di N. A volte un simbolo puà non corrispondere a nessuna scelta se sono disponibili troppo poche scelte nella configurazione. In questo caso l'indirizzo non è valido e non corrisponde a nessun nodo. Il nastro 3 contiene una stringa in Σb. Rappresenta il ramo della computazione di N dalla radice al nodo indirizzato da questa stringa, a meno che l'indirizzo non sia non valido. La stringa vuota è l'indirizzo della radice dell'albero. Ora siamo pronti a descrivede D.

  1. Inizialmente il nastro 1 contiene l'input w e i nastri 2 e 3 sono vuoti.
  2. Copia il nastro 1 nel nastro 2
  3. Usa il nastro 2 per simulare N on l'input w di uno dei rami della computazione nondeterministica. Prima di ogni passo di N consulta il prossimo simbolo nel nastro 3 per determinare quale scelta fare tra quelle permesse dalla funzione di transizione di N. Se non restano più simboli nel nastro 3 o se la scelta nondeterministica non è valida, annullare questo ramo andando al passo 4. Andare al passo 4 anche se si incontra una configurazione rifiutata. Se si trova una configurazione accettata, considerare l'input accettato.
  4. Rimpiazzare la stringa nel nastro 3 con la prossima stringa lessicografica. Simulare il prossimo ramo della computazione di N andando al passo 2.

La simulazione di una TM nondeterministica è estremamente macchinosa e inefficiente (ma le TM non richiedono di essere efficienti), perché consiste in:

  1. calcolare il numero massimo di branch possibili, che nel libro è rappresentato dalla variabile b.
  2. Eseguire i vari passaggi seguendo l'ordine lessicograficamente. Questo significa che se b = 4 l'ordine che seguirò sarà 1, 2, 3, 4, 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33, 34, 41, 42, 43, 44, 111...
  3. Per ciascuno dei passaggi, copiare il nastro "matrice" nel nastro di "simulazione" ed eseguire DI NUOVO tutto il ramo partendo da zero fino ad arrivare al successivo livello.

Mi sembra di essere Bill Murray nel giorno della Marmotta:

Questa immagine, per motivi di Copyright, non è presente nel libro di Sipser

Corollaio 3.18

Un linguaggio è Turing-riconoscibile sse qualche macchina di Turing nondeterministica lo riconosce.

Prova

Ogni TM deterministica è automaticamente una TM nondeterministica, e così una delle due direzioni segue immediatamente. L'altra direzione segue dal teorema 3.16.

Corollario 3.19

Un linguaggio è decidibile sse una macchina di Turing nondeterministica lo decide.

Prova

La direzione "se" è provata dal fatto che se un linguaggio è decidibile, allora una macchina di Turing deterministica lo decide, e siccome una TM deterministica è equivalente in potenza a una TM nondeterministica (3.16) allora se un linguaggio è decidibile, esiste una macchina di Turing nondeterministica che lo decide.

La direzione "solo se" significa che se una macchina di Turing nondeterministica decide un linguaggio, allora è decidibile.

Rispetto alla TM deterministica costruita per 3.16, per una TM decidibile dobbiamo aggiungere un nuovo passo che dice che se nessuno dei rami si conclude con un'accettazione, avremo uno stato reject.

Discutiamo se questa nuova macchina D2 è un decisore per L. Se N accetta gli input, D2 tutti i rami si fermano e fanno un reject, perché è un decisore. Quindi ogni ramo ha una quantità finita di nodi, dove ogni nodo rappresenta on passaggio della computazione di N lungo il ramo.

Perciò l'intero albero di computazione di N nel suo input è finito, in virtù del teorema sugli alberi dato nel corpo dell'esercizio. Conseguentemente, D si fermerà e farà un reject quantdo questo intero albero sarà stato esplorato.

Teorema 3.13

Ogni macchina di Turing multinastro ha una macchina di Turing a singolo nastro equivalente.

Prova

Mostriamo come convertire una macchina di Turing multinastro M in una macchina di Turing S a singolo nastro equivalente. L'idea è di mostrare come simulare M con S.

Diciamo che M ha k nastri. Allora S simula l'effetto di k nastri memorizzando le sue informazioni in un singolo nastro. Usa il nuovo simbolo # come delimitatore per separare i contenuti di diversi tipi di nastro. In più, oltre ai contenuti dei singoli nastri, S deve tenere traccia delle posizioni delle rispettive testine. Lo fa scrivendo un simbolo con un punto sopra per marcare il punto in cui è la testina del nastro. Come prima, il simbolo "puntato" è un nuovo simbolo che deve essere aggiunto all'alfabeto del nastro. Pensiamo a questi come "nastri e testine virtuali".

Corollario 3.15

Un linguaggio è Turing-riconoscibile sse qualche macchina di Turing multinastro lo riconosce.

Prova

Un linguaggio riconoscibile da Turing è riconosciuto da una macchina di Turing ordinaria (singolo nastro), che è un caso speciale delle macchine di Turing multinastro. Questo prova una direzione del corollario. L'altra consegue da 3.13.

Tabella di concetti per reti di calcolatori

Definire i seguenti concetti:

 

Concetto Spiegazione Note
Segnale Grandezza fisica che varia nel tempo per trasmettere informazione
Mezzo trasmissivo Il canale attraverso cui è veicolato il segnale Cavo
Fibra ottica
Etere (wifi)
Velocità di trasmissione Quantità di informazioni che è possibile veicolare in un determinato lasso di tempo Prima della propagazione: è una "capienza" che non ha relazione con la velocità di propagazione
Velocità di propagazione Velocità in cui il segnale si trasmette attraverso il mezzo
Modulazione del segnale Variazione della frequenza, dell'ampiezza o della fase di un'onda (portante)
Banda Sinonimo di velocità di trasmissione
Banda passante Intervallo di frequenze che il segnale contiene o che il dispositivo è in grado di trattare
Banda trasmissiva
Jitter Variazione nei ritardi dei pacchetti
Throughput Quantità di dati effettivamente trasmessa. Tiene conto del protocollo usato.
Lunghezza di un bit
Baud Numero di simboli inviati al secondo
Bit rate Numero di bit inviati al secondo
Datagram Pacchetto dati di dimensioni limitate contenente mittente e destinatario

 

exercise 2.30

a.

Use the pumping lemma to show that the following language is not context free:
L = {0n1n0n1n| n ≥ 0}

We'll show that L is not a context free language using the pumping lemma. We suppose that L is CFL and we'll prove that we'll have contradictions in any case.

Since we supposed that L is a CFL, we can write the language in form of uvixyiz. The constraint are that i ≥ 0, and there are a number p (the "pumping length") where |vy|>0 and |vxy|≤p.

So, let we choose the string 0p1p0p1p, that is evidently more long than p. There are two cases:

  1. v contains only 0s or 1s. In this case, pumping the string make a new string with a different number of 0s than 1s, and it's not recognized by L. Similar for y.
  2. v contains both 0s and 1s. In this case pumping the string make a new string with perhaps the same number of 0s and 1s, but in disorder, so it's not recognized by L. Similar for y.

In any case we obtain a contradiction, so we proved that "L is a CFL" is false, then L is not a CFL. ☐

b.

Use the pumping lemma to show that the following language is not context free:
L = {0n#02n#03n| n ≥ 0}

We'll show that L is not a context free language using the pumping lemma. We suppose that L is CFL and we'll prove that we'll have contradictions in any case.

Since we supposed that L is a CFL, we can write the language in form of uvixyiz. The constraint are that i ≥ 0, and there are a number p (the "pumping length") where |vy|>0 and |vxy|≤p.

So, let we choose the string 0p#02p#03p, that is evidently more long than p. There are two cases:

  1. v contains a #. In this case, pumping the string make a new string with a uncorrect number of #, and it's not recognized by L. Similar for y.
  2. v contains only 0s. In this case pumping the string make a new string with a number of 0 that doesn't respect the ratio 1:2:3, so it's not recognized by L. Similar for y.

In any case we obtain a contradiction, so we proved that "L is a CFL" is false, then L is not a CFL. ☐

c.

Use the pumping lemma to show that the following language is not context free:
L = {w#t| w is a substring of t, where w, t ∈ {a, b}*}

We'll show that L is not a context free language using the pumping lemma. We suppose that L is CFL and we'll prove that we'll have contradictions in any case.

Since we supposed that L is a CFL, we can write the language in form of uvixyiz. The constraint are that i ≥ 0, and there are a number p (the "pumping length") where |vy|>0 and |vxy|≤p.

So, let we choose the string apbp#apbp, that is evidently more long than p. There are three cases:

  1. v or y contain a #. In this case, pumping the string make a new string with a uncorrect number of #, and it's not recognized by L.
  2. v or y are at the left part of the string. In this case, pumping up v or y we can obtain a string longer than the right part, that is not recognized by L.
  3. v or y are at the right part of the string. In this case, pumping down v or y we can obtain a string shorter than the left part, that is not recognized by L.

d.

Use the pumping lemma to show that the following language is not context free:
L = {t1#t2# · · · #tk| k ≥ 2, each ti ∈ {a, b}*, and ti = tj for some i ≠ j}

Use the pumping lemma to show that the following language is not context free:
L = {w#t| w is a substring of t, where w, t ∈ {a, b}*}

We'll show that L is not a context free language using the pumping lemma. We suppose that L is CFL and we'll prove that we'll have contradictions in any case.

Since we supposed that L is a CFL, we can write the language in form of uvixyiz. The constraint are that i ≥ 0, and there are a number p (the "pumping length") where |vy|>0 and |vxy|≤p.

So, let we choose the string qp1#qp2# · · · #qpk where k ≥ 2 and q is the string t = {0,1}* and the length of t is p, that is evidently more long than p. There are two cases:

  1. v or y contain only #. In this case, pumping the string make a new string with a uncorrect number of #, and it's not recognized by L.

[to be continued...]

 

Suggerimenti per PDA e CFG

Quando si deve dare una CFG, oltre alle regole, fare anche un esempio di parsing.

Se è richiesto un caso particolare (es. se una CFG è ambigua, o l'applicazione a una stringa data) va messo l'albero di derivazione.

L'albero deve includere le ε, se richieste, e il simbolo iniziale.

Esempio: {aibjck | i = j or j = k, where i, j, k ≥ 0}

S = D | E

D = Dc | Fc

E = aE | aG

F = aFb | ε

G = bGc | ε

Dire se la grammatica è ambigua

       S               S
       |               |
       D               E
   +---+---+       +---+---+
   D       c       a       E
+--+--+                +---+---+
a  D  b                b   E   c
   |                       |
   ε                       ε

Quando chiede di dimostrare qualcosa usando dei linguaggi, non dare per scontato che siano context-free.

Usare una grammatica o un PDA per dimostrare che lo sono.

USARE GRAMMATICHE E NON PDA PER DIMOSTRARE COSE.

Quando si uniscono o concatenano grammatiche diverse, fare attenzione al nome dei terminali: se due terminali in grammatiche diverse hanno lo stesso nome, fondendo le grammatiche si uniscono anche i nomi dei terminali!

Se necessario, aggiungere pedici con un numero progressivo.

Esempio:

G: S1 → A, A → aB, B → bB|ε

H: S2 → AB, A → c, B → d

l'unione può  portare a S → S1 → A → c, che è palesemente un comportamento indesiderato.

exercise 2.16

Show that the class of context-free languages is closed under the regular operations, union, concatenation, and star.

After the meeting with Calzavara, we'll rewrite the proofs using the grammars instead of PDAs

 

Union

Let A, B be CFLs, then exist G, H CFGs when L(G) = A and L(H) = B. Let S1, S2 the start symbols for G and H.

We can build a new CFG with start symbol S where S → S1 | S2, including all the productions of G and H.
Before the union, we must ensure that the terminals in G and H are different, by replacing the common names.

Concatenation

Let A, B be CFLs, then exist G, H CFGs when L(G) = A and L(H) = B. Let S1, S2 the start symbols for G and H.

We can build a new CFG with start symbol S where S → S1 S2, including all the productions of G and H.
As the union, we must ensure that the terminals in G and H are different.

Star

Let A be CFL, then exist G CFG when L(G) = A. Let S1 the start symbols for G.

We can build a new CFG with start symbol S where S → S S1|ε, including all the productions of G.

ε warrantees that the recursion ends and that the new CFG accepts an empty string.


OLD VERSION

Union

Proof idea

Union of two PDAs can be similar to the union of two NFA: a new start state points to both the old start states with an ε arrow. What about the stack? Since it's empty - by definition of PDA - at the new start state, the two arrows must not read or write anything from the stack, to be sure to keep the old starts states with an empty stack.

The union of two NFAs, used to prove the closure for the CFLs

Proof

Let be A1, A2 two context-free languages. If A1 and A2 are context-free, there exists two CFG N1, N2 that recognize them. We define N1, N2 as follow:

N1 = {Q1, Σ, Γ1, δ1, q1-start, F1⊆Q1}

N2 = {Q2, Σ, Γ2, δ2, q2-start, F2⊆Q2}

Construct N that recognize A1 ∪ A2 as
N = {Q, Σ, Γ, δ, qstart, F⊆Q}
where

Q = Q1 ∪ Q2 ∪ qstart

Γ = Γ1 ∪ Γ2

qstart = "new" start state for N

F = F1 ∪ F2

δ = (for a ∈ Σ and b ∈ Γ)

  • δ(q1, a, b) if q ∈ Q1
  • δ(q2, a, b) if q ∈ Q2
  • {q1, q2} if q = qstart and a = ε
  • ∅ if q = qstart and a ≠ ε

Note that the stack is managed independently for each automaton N1 and N2

Concatenation

Proof idea

As for the union, we can start our proof using the concatenation proof for the NFAs, that consists in linking all the final states of the "first" NFA to the start state of the "second".

The concatenation of two NFAs, used to prove the closure of the CFLs

Can we be sure that at the final state the stack is empty in every case? That's an open question.

If yes, the proof idea is completed.

If not, we must add a state that loops the stack in order to empty it. This state, accepting an empty string, reads all the symbols in Γ except $, where $ is the placeholder for the end of the stack, and then goes to the next PDA where the stack contains $. This is a little tricky, but guarrantees that the stack is empty when the second PDA starts.

Proof

Let be A1, A2 two context-free languages. If A1 and A2 are context-free, there exists two CFG N1, N2 that recognize them. We define N1, N2 as follow:

N1 = {Q1, Σ, Γ1, δ1, q1-start, F1⊆Q1}

N2 = {Q2, Σ, Γ2, δ2, q2-start, F2⊆Q2}

Construct N that recognize A1 ○ A2 as
N = {Q, Σ, Γ, δ, qstart, F⊆Q}
where

Q = Q1 ∪ Q2 ∪ qdiscard

Γ = Γ1 ∪ Γ2

qstart = q1-start

F = F2

δ = (for a ∈ Σ and b ∈ Γ)

  • δ(q1, a, b) if q ∈ Q1 and q ∉ F
  • δ(q1, a, b) if q ∈ Q1 and q ∈ F and a ≠ ε
  • δ(q1, a, b) ∪ qdiscard if q ∈ Q1 ∪ qdiscard and a = ε and b ≠ $
  • q2-start if q ∈ Q1∪ qdiscard and a = ε and b = $
  • δ(q2, a, b) if q ∈ Q2

Star

Proof idea

As for the union, we can start our proof using the star proof for the NFAs, that consists in:

  • create a new start state (accepted) that goes to the old start state with a ε arrow
  • create one ε arrow for each accepted state to the old start state

As for the concatenation, we must be sure that the stack is empty before go to the old start state again.

The star of a NFA, used to prove the closure of the CFLs

So, before return to the old start state we must add a new state qdiscard that reads all the symbols in Γ except $.

Proof

Let be A1 a context-free language. If A1 is context-free, there exists a CFG N1 that recognize it. We define N1 as follow:

N1 = {Q1, Σ, Γ1, δ1, q1-start, F1⊆Q1}

Construct N that recognize A1* as
N = {Q, Σ, Γ, δ, qstart, F⊆Q}
where

Q = Q1∪ qstart

Γ = Γ1

qstart is the new start

F = F1∪ qstart

δ = (for a ∈ Σ and b ∈ Γ)

  • δ(q1, a, b) if q ∈ Q1 and q ∉ F
  • δ(q1, a, b) if q ∈ Q1 and q ∈ F and a ≠ ε
  • δ(q1, a, b) ∪ qdiscard if q ∈ Q1 ∪ qdiscard and a = ε and b ≠ $
  • q2-start if q ∈ Q1∪ qdiscard and a = ε and b = $
  • ∅ if q = qstart and a ≠ ε

exercise 2.9

Give a context-free grammar that generates the language
A = {aibjck| i = j or j = k where i, j, k ≥ 0}.
Is your grammar ambiguous? Why or why not?

Answer

S = D|C|ε
D = Bc|Dc
C = aA|aC
B = aBb|ε
A = bAc|ε

The grammar is ambiguous because we can build two different trees if the number of as, bs, cs are the same: in this case we can consider pairs of abs and then cs or pairs of bcs and then as as prefixes.

exercise 2.2

a. Theorem

Use the languages A = {ambncn| m, n ≥ 0} and B = {anbncm| m, n ≥ 0}
together with Example 2.36 to show that the class of context-free languages
is not closed under intersection.

a. Proof

The intersection of two languages is when a string is recognized both by the first and the second. If a string w is recognized by A, this means that it has the same number of bs and cs; if the string w is recognized by B, this means that it has the same number of as and bs. If w is recognized by the intersection of the two languages, this means that it has the same number of bs and cs and the same number of as and bs, so m = n and the number of as, bs and cs is the same.

A ∩ B = {anbncn| n ≥ 0}

This is exactly the language of the example 2.36.

Lemma: C = {anbncn| n ≥ 0} that isn't context-free.

We can assume that C = {anbncn| n ≥ 0} is context-free to obtain a contradiction.

Let p the pumping length for C that is guarranteed to exist by the pumping lemma. Select the string s = apbpcp. Clearly, s is a member of C and s is not shorter than p.

The pumping lemma states that s can be pumped, but we show that it cannot. In other words, we show that no matter how we divide s into uvxyz, one of the three conditions of the lemma is violated.

    1. for each i ≥ 0, uvixyiz ∈ A
    2. |vy| > 0
    3. |vxy| ≤ p

the condition 2. affirms that v and y are nonempty. We consider one of two cases, depending on whether substring v and y contains the same symbol or not.

  1. If v contains the same symbol, v must contain only as or bs or cs, and the same holds for y. So pumping up the string, we don't have the same number of as, bs and cs yet. This is a violation of the first condition.
  2. If v and y contains more than one symbol, pumping up uvixyiz can bring to the same number of as, bs, and cs, but the order will be uncorrect. Again, this is a violation of the first condition.

In both cases we obtain a contradiction, so we can say that CFLs are not closed under intersection. ☐

b. Theorem

Use part (a) and DeMorgan’s law (Theorem 0.20) to show that the class of context-free languages is not closed under complementation.

b. Proof

If CFL were closed under complementation, A is CFL ⇔ ¬A is CFL and B is CFL ⇔ ¬B is CFL. But ¬A ∩ ¬B is not a CFL, as proved before.

Using the DeMorgan's law, that says

¬A ∩ ¬B = ¬(A ∪ B)

we can say that ¬(A ∪ B) is not a CFL, even if A ∪ B is it (see exercice 2.16).

So, we can say that CFLs are not closed under complementation. ☐

Equivalenza tra PDA e Grammatiche Context Free (CFG)

Traduzione non autorizzata delle pagine del capitolo 2.2 di Sipser. In blu, i miei commenti.

In questa sezione mostriamo che le grammatiche context-free e gli automi pushdown sono equivalenti nelle loro potenzialità. Entrambi sono in grado di descrivere la classe dei linguaggi context-free. Mostriamo come convertire ogni grammatica context-free in un automa pushdown che riconosce lo stesso linguaggio e viceversa. Ricordiamo che abbiamo definito un linguaggio context-free come un linguaggio che può essere descritto con una grammatica context-free, il nostro obiettivo nel teorema seguente.

2.20 Teorema

Un linguaggio è context-free se e solo se un automa pushdown lo riconosce.

Come sempre, quando c'è un "se e solo se" in un teoriema, abbiamo due direzioni da provare. In questo teorema entrambe le direzioni sono interessanti (=incasinate). Prima, facciamo la direzione "se", più facile.

2.21 Lemma

Se un linguaggio è context-free, allora un automa pushdown lo riconosce.

Idea

Sia A un CFL. Dalla definizione, sappiamo che A ha una CFG, G, che lo genera. Mostriamo come convertire G in un PDA equivalente, che chiamiamo P.

Il PDA P che ora descriviamo accetta i suoi input w, se G genera questo input, determinando se c'è una derivazione per w. Ricordiamo che una derivazione è semplicemente la sequenza di sostituzioni fatte allo stesso modo in cui una grammatica genera una stringa. Ogni passo della derivazione produce una stringa intermedia di variabili e terminali. Disegnamo P per determinare se qualche serie di sostituzioni, usando le regole di G, possono condurre dalla variabile di partenza a w.

Una delle difficoltà nel testare se c'è una derivazione per w è immaginare quali sostituzioni fare. Il nondeterminismo del PDA permette di indovinare la sequenza di sostituzioni corrette. A ogni passaggio della derivazione, una delle regole per una variabile particolare è selezionata nondeterministicamente e usata per sostituire questa variabile.

Il PDA P inizia scrivendo la variabile di partenza nel suo stack. Passa attraverso una serie di stringhe intermedie, facendo una sostituzione dopo l'altra. Eventualmente può arrivare a una stringa che contiene solo simboli terminali, che significa che ha usato la grammatica per derivare la stringa (bingo!). Allora P accetta se la stringa è identica a quella che ha ricevuto in input.

Implementare questa strategia su un PDA richiede un'idea addizionale. Abbiamo bisogno di vedere come il PDA memorizza la stringa intermedia per andare da una a un'altra. Usare semplicemente lo stack per memorizzare ogni stringa intermedia è una tentazione. Però questo non funzione bene, perché il PDA ha bisogno di trovare la variabile nella stringa intermedia e fare sostituzioni. Il PDA può accedere solo al simbolo in cima allo stack e che può essere un simbolo terminale dentro una variabile. Il modo per aggirare il poblema è tenere solo una parte della stringa intermedia nello stack: i simboli con cui inizia la prima variabile nella stringa intermedia. Ogni simbolo terminale che appare prima della prima variabile è messa in corrispondenza immediatamente con i simboli nella stringa di input. La figura seguente illustra il PDA P.

Figura 2.22: P rappresenta la stringa intermedia 01A1A0

Di seguito, una descrizione informale di P.

  1. Metti il simbolo marcatore $ e la variabile di partenza nello stack
  2. Ripeti i seguenti passi all'infinito
    1. se la cima dello stack è una variabile simbolo A scegliere nondeterministicamente una delle regole per A e sostituire A con la stringa sul lato destro della regola
    2. se la cima dello stack è il simbolo terminale a, leggere il simbolo successivo dall'input e confrontarlo con a. Se è lo stesso, ripetere. Se non è lo stesso, rigettare questo ramo del nondeterminismo
    3. se la cima dello stack è il simbolo terminale $, entrare nello stato accettato. Facendo così, si accetta l'input se è stato letto interamente.

Qui manca un esempio, perché non si capisce molto.

Immaginiamo un PDA fatto così:

S → aAb

A → # | aAa

La stringa aa#ab è riconosciuta? Servono alcuni passaggi: aaAab (A = #), aAb (A = aAa), S (S = aAb), per cui va mantenuta la stringa intermedia.

  1. metto nello stack il simbolo di dollaro $ seguito da aAb, cioè la variabile di partenza, esclusi i terminali a destra. Il mio stack contiene $aA, e siccome è una LIFO, estraggo nell'ordine Aa$
  2. la cima dello stack è una variabile, quindi nondeterministicamente sostituisco A con # e aAa in due diversi branch
    1. # ⇒ nello stack ho #a$, ma quando confronto a#b con la mia stringa, ottengo una differenza, poiché il secondo carattere non è # ma a
    2. aAa => nello stack ho aAaa$, quindi la mia stringa completa è aaAab, ma quando vado a ricontrollarla sostituisco nondeterministicamente A con # e con aAa
      1. # ⇒ ottengo aa#ab, che è la mia stringa
      2. aAa ⇒ scarto questa opzione perché otterrei aaaAaab, ma il terzo carattere è # e non a.

Non ho capito ancora in che modo funziona lo scarico/carico dello stack.

Prova

Ora diamo un dettaglio formale della costruzione dell'automa pushdown P = (Q, Σ, Γ, δ, q1, F) . Per fare una costruzione più chiara, usiamo l'abbreviazione per la funzione di transizione. QUesta notazione fornisce un modo per scrivere una stringa intera nello stack in un passaggio della macchina. Possiamo simulare questa azione introducendo degli stati addizionali per scrivere la stringa un simbolo alla volta, come implementato nella seguente costruzione formale.

Siano q e r stati del PDA e sia a in Σε e s sia in Γε. Vogliamo che il PDA vada da q a r e legge a ed estrae s. Inoltre vogliamo che allo stesso tempo si spinga la stringa intera u = u1...ul nello stack. Possiamo implementare questa azione introducendo dei nuovi stati q1, ..., ql-1 e impostando la funzione di transizione in questo modo:

δ(q, a, s) per contenere (q1, ul),
δ(q1, ε, ε) = {(q2, ul-1)},
δ(q2, ε, ε) = {(q3, ul-2)},
δ(q3, ε, ε) = {(q4, ul-2)},
...
δ(ql-1, ε, ε) = {(r, u1)}.

Usiamo la notazione (r, u) ∈ δ(q, a ,s) per dire che quando q è lo stato dell'automa, a è il prossimo simbolo di input, s è il simbolo in cima allo stack, il PDA può leggere la a e prelevare la s, allora inserisce la stringa u nello stack e va allo stato r. La figura seguente mostra questa implementazione:

Figura 2.23: implementazione dell'abbreviazione (r, xyz) ∈ δ(q, a, s)

Gli stati di P sono Q = {qstart, qloop, qaccept} ∪ E, dove E è l'insieme di stati di cui abbiamo bisogno per implementare la scorciatoria appena descritta. Lo stato di inizio è qstart. L'unico stato accettato è qaccept.

La funzione di transizione è definita di seguito. Cominciamo inizializzando lo stack perché contenga i simboli $ e S, implementando il passo 1 nella descrizione informale: δ(qstart, ε, ε) = {(qloop, S$)}. Poi facciamo le transizioni per il ciclo principale del passo 2.

Prima ci occupiamo del caso (a), se la cima dello stack contiene una variabile. Sia δ(qloop, ε, A) = {(qloop, w) | dove A → w è una regola in R}.

Secondo, gestiamo il caso (b), se la cima dello stack contiene un terminale. Si ha che δ(qloop, a, a) = {(qloop, ε)}.

Infine, gestiamo il caso (c), se il marcatore di stack vuoto $ è in cima allo stack. Si ha che δ(qloop, ε, $) = {(qaccept, ε)}.

Il diagramma di stato è mostrato nella figura 2.24.

Figura 2.24: il diagramma di stato di P

Questo completa la prova del lemma 2.21.

La seconda parte la farò se e quando lo riterrò utile