Calcolabilità e linguaggi formali, Page 2 Categoria

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 S₁, S₂ the start symbols for G and H.

We can build a new CFG with start symbol S where S → S₁ | S₂, 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 S₁, S₂ the start symbols for G and H.

We can build a new CFG with start symbol S where S → S₁ S₂, 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 S₁ the start symbols for G.

We can build a new CFG with start symbol S where S → S S₁|ε, 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.

Proof

Let be A₁, A₂ two context-free languages. If A₁ and A₂ are context-free, there exists two CFG N₁, N₂ that recognize them. We define N₁, N₂ as follow:

N₁ = {Q₁, Σ, Γ₁, δ₁, q_1-start, F₁⊆Q₁}

N₂ = {Q₂, Σ, Γ₂, δ₂, q_2-start, F₂⊆Q₂}

Construct N that recognize A₁ ∪ A₂ as
N = {Q, Σ, Γ, δ, q_start, F⊆Q}
where

Q = Q₁ ∪ Q₂ ∪ q_start

Γ = Γ₁ ∪ Γ₂

q_start = "new" start state for N

F = F₁ ∪ F₂

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

• δ(q₁, a, b) if q ∈ Q₁
• δ(q₂, a, b) if q ∈ Q₂
• {q₁, q₂} if q = q_start and a = ε
• ∅ if q = q_start and a ≠ ε

Note that the stack is managed independently for each automaton N₁ and N₂

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".

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 A₁, A₂ two context-free languages. If A₁ and A₂ are context-free, there exists two CFG N₁, N₂ that recognize them. We define N₁, N₂ as follow:

N₁ = {Q₁, Σ, Γ₁, δ₁, q_1-start, F₁⊆Q₁}

N₂ = {Q₂, Σ, Γ₂, δ₂, q_2-start, F₂⊆Q₂}

Construct N that recognize A₁ ○ A₂ as
N = {Q, Σ, Γ, δ, q_start, F⊆Q}
where

Q = Q₁ ∪ Q₂ ∪ q_discard

Γ = Γ₁ ∪ Γ₂

q_start = q_1-start

F = F₂

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

• δ(q₁, a, b) if q ∈ Q₁ and q ∉ F
• δ(q₁, a, b) if q ∈ Q₁ and q ∈ F and a ≠ ε
• δ(q₁, a, b) ∪ q_discard if q ∈ Q₁ ∪ q_discard and a = ε and b ≠ $
• q_2-start if q ∈ Q₁∪ q_discard and a = ε and b = $
• δ(q₂, a, b) if q ∈ Q₂

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.

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

Proof

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

N₁ = {Q₁, Σ, Γ₁, δ₁, q_1-start, F₁⊆Q₁}

Construct N that recognize A₁* as
N = {Q, Σ, Γ, δ, q_start, F⊆Q}
where

Q = Q₁∪ q_start

Γ = Γ₁

q_start is the new start

F = F₁∪ q_start

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

• δ(q₁, a, b) if q ∈ Q₁ and q ∉ F
• δ(q₁, a, b) if q ∈ Q₁ and q ∈ F and a ≠ ε
• δ(q₁, a, b) ∪ q_discard if q ∈ Q₁ ∪ q_discard and a = ε and b ≠ $
• q_2-start if q ∈ Q₁∪ q_discard and a = ε and b = $
• ∅ if q = q_start and a ≠ ε

Give a context-free grammar that generates the language
A = {aⁱb^jc^k| 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.

a. Theorem

Use the languages A = {a^mbⁿcⁿ| m, n ≥ 0} and B = {aⁿbⁿc^m| 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 = {aⁿbⁿcⁿ| n ≥ 0}

This is exactly the language of the example 2.36.

Lemma: C = {aⁿbⁿcⁿ| n ≥ 0} that isn't context-free.

We can assume that C = {aⁿbⁿcⁿ| 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 = a^pb^pc^p. 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. 1. for each i ≥ 0, uvⁱxyⁱz ∈ 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 uvⁱxyⁱz 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. ☐

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.

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, Σ, Γ, δ, q₁, 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 = u₁...u_l nello stack. Possiamo implementare questa azione introducendo dei nuovi stati q₁, ..., q_l-1 e impostando la funzione di transizione in questo modo:

δ(q, a, s) per contenere (q₁, u_l),
δ(q₁, ε, ε) = {(q₂, u_l-1)},
δ(q₂, ε, ε) = {(q₃, u_l-2)},
δ(q₃, ε, ε) = {(q₄, u_l-2)},
...
δ(q_l-1, ε, ε) = {(r, u₁)}.

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:

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

La funzione di transizione è definita di seguito. Cominciamo inizializzando lo stack perché contenga i simboli $ e S, implementando il passo 1 nella descrizione informale: δ(q_start, ε, ε) = {(q_loop, 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 δ(q_loop, ε, A) = {(q_loop, w) | dove A → w è una regola in R}.

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

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

Il diagramma di stato è mostrato nella figura 2.24.

Questo completa la prova del lemma 2.21.

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

Ieri siamo andati a parlare con il prof Calzavara e abbiamo raccolto un'importante indicazione sull'applicazione del pumping lemma.

1. Non fare l'errore di applicare il PL a un esempio, "dimenticandosi" di includere la lunghezza p nella dimostrazione.

Per esempio, la soluzione di 1.49/b non può essere di prendere una stringa 1111010101... perché presuppone che p≤4, ma non prova niente nel caso in cui p>4.

Un'idea di fondo più "solida" sarebbe dire che abbiamo una stringa 1^p01^p che sicuramente è più lunga di p, e la cui parte sinistra sia xy, mentre z è la parte a destra dello zero. Facendo il pumping up si arriva ad avere un numero di 1 a sinistra maggiore del numero di 1 a destra, che contraddice la definizione del linguaggio.

2. Il costrutto contrario di "per tutti esiste uno" è "per qualcuno non esiste nessuno".

Non è sufficiente trovare un caso in cui qualcosa non funziona, ma bisogna trovare un caso in cui niente funziona.

3. In ogni caso, quando si parla di pumping lemma più che dividere la stringa in tre parti è meglio valutare se dividerla in una "parte sinistra" pompabile e una parte destra.

Più che cercare di definire quale sia la suddivisione in xyz, è meglio definire le caratteristiche che dovrebbe avere questa suddivisione.

4. Il pumping lemma nei linguaggi context-free è più complicato, perché non c'è più una "parte sinistra" pompabile, ma c'è una suddivisione in cinque della stringa per cui la zona pompabile diventa quella centrale.

Use the pumping lemma to show that the following languages are not regular.
a. A₁ = {0ⁿ1ⁿ2ⁿ| n ≥ 0}
b. A₂ = {www | w ∈ {a, b}^∗}
c. A₃ = {a²ⁿ| n ≥ 0} (Here, a²ⁿ means a string of 2ⁿ a’s.)

a. Theorem

A₁ = {0ⁿ1ⁿ2ⁿ| n ≥ 0} is not regular.

a. Proof

Applying the pumping lemma to a string that matches with A₁ we can have two scenarios:

1. y is composed by only 0s or 1s or 2s. For example, 012 with y = 1. When we change the number of ys, we obtain a different number of 1s than others: 02, 0112, 01112, ..., and this doesn't match with A₁ anymore
2. y is composed by a pair or more of numbers. For example, 001122, with y = 0011. Changing the number of ys, the order of the numbers are not kept: 22, 0011001122, 00110011001122...

so A₁ is not regular.

b. Theorem

A₂ = {www | w ∈ {a, b}^∗} is not regular.

b. Proof

We show that choosing a pattern w, composed by as and bs, the language A₂, that recognizes the pattern w repeated three times, is not regular.

If the y part of the pumping lemma is composed by a substring of w, repeat the y more times means don't match A₂ anymore, because the string can be composed by other than ws. I.E. w = aab, a valid string is aabaabaab, y = the central pair aa: repeating y, we obtain: aabbaab (0 times), aabaabaab (matches), aabaaaabaab (1 time). The first and the third examples are not composed by ws.

If the y part of the pumping lemma is exactly w, repeat the y a number of times different by 1 mod 3 (1, 4, 7, 10...) doesn't match the rule of three times w. I.E. w = aab, y = aab ⇒ aabaab (0 times, doesn't match); aabaabaab (1 time, matches), aabaabaabaab (2 times, doesn't match)...

So, A₂ is not regular.

c. Theorem

A₃ = {a²ⁿ| n ≥ 0} (Here, a²ⁿ means a string of 2ⁿ a’s.)

c. Proof

A₃ recognizes a, aa, aaaa, aaaaaaaa, ...

Choose x = a, y = aa, z = a seems a good idea, because we're sure that every string recognized by A₃ is writable with an xyⁱz, but there are two problems: a single "a" is not writable with this pattern, and there are strings that are writable but don't be recognized by A₃, for example, i = 2 ⇒ a aa aa a (the spaces have been added to make the string more readable).

Choosing a simpler definition of x, y, z, as x = ε, y = a, z = ε, we are affected by the same problem.

a. Theorem

Let B = {1^ky|y∈{0,1}* and y contains at least k 1s, for k ≥ 1}. Show that B is a regular language.

a. Proof

B equals to "Let B is a string that begins with 1 and, after, contains at least another 1".

This DFA doesn't "count" the number of 1s

b. Theorem

Let B = {1^ky|y∈{0,1}* and y contains at most k 1s, for k ≥ 1}. Show that B is not a regular language.

b. Proof

As shown in 1.77 Sipser's example, we can apply an absurd proof of the pumping lemma to this language

Let we assume that B is regular. Let we choose one 1 as pumping's y and the second part (i.e. from the first 0 found) as pumping's z, and it seems to work:

$\underset{y}{\underbrace{1111}}\underset{z}{\underbrace{0100}}$

or better

$\underset{y_1}{\underbrace{1}}\underset{y_2}{\underbrace{1}}\underset{y_3}{\underbrace{1}}\underset{y_{\mathrm{n}}}{\underbrace{1}}\underset{z}{\underbrace{0100}}$

Pumping lemma doesn't allows a length of 0 for the y part, but allows that y is repeated zero times.

Using as example the previous string, with y repeated zero times, we obtain the string 0100, that doesn't match. Thus we obtain a contradiction.

Un linguaggio regolare finito riconosce un insieme finito di stringhe.

Posso costruire un automa sotto forma di albero in cui il percorso più lungo corrisponde alla stringa più lunga.

Quindi è possibile costruire un automa il cui numero massimo di stati è la lunghezza della stringa più lunga per il numero di lettere.

Un linguaggio finito è sempre regolare (senza loop).

Un linguaggio con loop è non regolare se contraddice il pumping lemma.

Un linguaggio con loop che rispetta il pumping lemma può essere o non essere regolare.

https://www.geeksforgeeks.org/theory-of-computation-pumping-lemma/

Il pumping lemma è una cavolata, espressa in una maniera complicata perché formale.

Ogni stringa sposta l'automa da uno stato all'altro, ma se ci sono più lettere che stati è ovvio che perché la stringa sia riconosciuta bisogna che ripeta più volte il passaggio attraverso alcuni stati.

Gli angolofoni lo chiamano principio dei buchi della piccionaia, noi principio dei cassetti, ma il senso non cambia.

In pratica quindi:

1. for each i ≥ 0, xyⁱz ∈ A significa che A contiene xz, xyz, xyyz, xyyyz, xyyyyz...
2. |y| > 0 significa, banalmente, che non posso scegliere ε come y, cioè devo avere un y che contiene qualcosa. Al limite, lo ripeto zero volte...
3. |xy| ≤ p significa che o p si ferma a x oppure è lungo almeno xy

Da questi tre punti si evince anche che:

1. x e z possono essere ε
2. se p > 0, allora o x o y devono essere diversi da ε