Calcolabilità: date una medaglietta a quell'uomo

18.

Bleah.

Superato, ma bleah.

Se tornassi indietro:

  1. Ripetere, ripetere a memoria. Capire è bene, ma per questo esame, impostato in questa maniera, conta molto il ripetere i teoremi e le loro dimostrazioni fino a saperle come l'ave maria. Questo è un mio punto debole (anche la memoria, intendo)
  2. Leggere attentamente, fare attenzione al fatto che automa, linguaggio, classe di linguaggi sono concetti molto diversi, anche se trattati in maniera sottilmente confusa, perché spesso si considerano intercambiabili.

In particolare, gli insiemi R (grammatiche regolari) e C (grammatiche context-free) si intesecano in modo diverso da L(R) e L(C).

Quindi, festeggiamo perché siamo arrivati a -1, ma con spumante svampito.

Fac simile del compito di calcolabilità e linguaggi formali

Esercizio 1

Dimostrare che la classe dei linguaggi regolari è chiusa rispetto a concatenazione.

Risposta

La soluzione è esattamente la dimostrazione del libro Sipser 1.47

Esercizio 2

Si consideri la seguente grammatica context-free G:

S → aSc | A
A → bAc | ε

Rispondere, fornendo opportune motivazioni, alle seguenti domande:

  1. La stringa abcc fa parte di L(G)?
  2. La stringa aaabcc fa parte di L(G)?
  3. Definire formalmente il linguaggio L(G)

Risposta

a. La stringa abcc fa parte di L(G) perché è possibile costruirla con il seguente albero:

          S
   +------+------+
   |      A      |
   |  +---+---+  |
   |  |   A   |  |
   |  |   |   |  |
   a  b   ε   c  c

b. La stringa aaabcc non fa parte di L(G) perché le regole di L(G) impongono che i due caratteri centrali, se esistono, siano bc, mentre questa stringa ha come caratteri centrali ab.

c. L(G) = ({S, A}, {a, b, c}, R, S)

dove R è l'insieme di regole

S → aSc | A
A → bAc | ε

Esercizio 3

Si consideri il linguaggio

EDFA = {〈A〉 | A è un DFA tale che L(A) = ∅}

Dimostrare che EDFA è decidibile.

Risposta

Idea: Per dimostrare che EDFA è decidibile bisogna che una macchina di Turing lo riconosca.

Si può vedere un DFA A come un grafo orientato e visitarlo partendo dallo stato start. Se al termine della visita non è stato toccato nessuno stato accepted, L(A) = ∅. In alternativa si può percorrere il grafo a ritroso partendo da ciascuno degli stati accepted e restituire accept quando si raggiunge lo stato start oppure reject se non lo si raggiunge mai. In altre parole, se lo stato start e almeno uno stato accepted sono collegati L(A) ≠ ∅, altrimenti L(A) = ∅

Prova: sia D un DFA e M una TM.

La TM accetta in input D e:

  1. marca lo stato start
  2. finché ci sono altri stati da marcare
    1. marca tutti gli stati che hanno una freccia entrante da uno degli stati marcati
  3. se uno stato accepted è marcato, accept; altrimenti reject.

Esercizio 4

Si consideri il linguaggio

A = {〈M〉 | M è un DFA che non accetta alcuna stringa con un numero dispari di 1}

Dimostrare che A è decidibile.

Risposta

Per dimostrare che A è decidibile è necessario costruire una TM che riconosca se un DFA riconosce una stringa con un numero dispari di 1.

A dispetto di quanto si può pensare, la TM non deve simulare il comportamento di un DFA con una stringa, perché alla TM viene passato solo il DFA, e non anche la stringa da testare, e testare una stringa qualunque con un numero pari di 1 o una sola con un numero dispari non è sufficiente a garantire che il DFA funzioni in un numero infinito di casi.

Bisogna affrontare questo problema cercando di dimostrare la proprietà del DFA, e non casi specifici. La TM prenderà quindi in input solo il DFA D, candidato a riconoscere la stringa con le caratteristiche richieste, e restituirà accepted se il DFA è in grado di rispondere o rejected se il DFA fa altro.

L'ambiguità di questo esercizio sta nel fatto che la dimostrazione non richiede di costruire una TM che sia in grado di simulare il DFA (in questo caso restituirebbe accepted con una stringa composta da un numero pari di 1), ma che sia in grado di capire se il DFA è in grado di farlo. Quindi non c'è nessuna stringa da passare, perché la TM non deve riconoscere la stringa!

Abbiamo due strumenti per capire se un DFA ha o non ha una caretteristica: EDFA e EQDFA. Bisogna quindi costruire uno dei due:

  • Un DFA D1 costruito in modo tale che, se il DFA D passato in input riconosce stringhe con numero pari di 1, allora D1 è vuoto. Questo ci permetterebbe di usare EDFA
  • Un DFA che riconosce stringhe con numero pari di 1. Questo ci permetterebbe di usare EQDFA
Strada EDFA

Dato l'alfabeto Σ = {0, 1} (la presenza di altri simboli oltre all'1 è poco rilevante), costruiamo un DFA D1 che riconosce il linguaggio 1(0∪11)*. Dal momento che DFA è chiuso per l'intersezione, se L(D) ∩ L(D1) = ∅ significa che D riconosce solo il complemento di D1 e quindi solo le stringhe con un numero di 1 pari.

La TM D1 prende in input un DFA D e procede così:

  1. interseca D con un DFA D1 tale che L(D1) = 1(0∪11)* e produce K
  2. Se EDFA a cui passiamo K restituisce accept, il DFA risponde al requisito dato e quindi accept; altrimenti reject.
Strada EQDFA

Dato l'alfabeto Σ = {0, 1} (la presenza di altri simboli oltre all'1 è poco rilevante), costruiamo un DFA D2 tale che L(D) = L(D2), cioè riconosce il linguaggio (0∪11)*.

La TM M2 prende in input un DFA D e procede così:

  1. Costruisce D2 che riconosce il linguaggio (0∪11)*
  2. Se EQDFA a cui passiamo D, D2 restituisce accept, il DFA risponde al requisito dato e quindi accept; altrimenti reject.

Suggerimenti del giorno

  1. Il compito è costituito da tre esercizi "semplici" di cui due dimostrazioni da imparare a memoria, un esercizio semplice, uno medio e uno più difficile.
  2. Ogni esercizio vale 6 punti, indipendentemente dalla difficoltà
  3. Quando si dimostra qualcosa è possibile appoggiarsi a teoremi già dimostrati nel libro, a patto di citarli correttamente, o per nome (es. ADFA) oppure usando una descrizione non ambigua (es. Il teorema che dimostra la riconoscibilità di un DFA)
  4. Ci sono tre tipi di strumento per la decidibilità: uno è A (riconoscibilità), che accetta un automa e una stringa, e due sono E (emptiness) e EQ (equivalenza, solo per linguaggi regolari), che accettano solo un automa. Quindi se non sono specificate stringhe, cioè la richiesta non riguarda la riconoscibilità, ma la decidibilità, bisogna usare gli operatori di unione, concatenamento, star e intersezione, complemento se supportati (no CFG) in maniera furba per arrivare ad applicare o E oppure EQ.
  5. La definizione di Σ spesso può non essere esplicita. Se va esplicitato, si può scrivere un'espressione che contiene:
    x where x ∈ {Σ \ 1}
    per indicare 1 o un altro simbolo qualunque
  6. Spiegare brevemente a parole la dimostrazione, in modo che in caso di errori sia chiaro il ragionamento sottostante.
  7. Non troveremo rice, perché renderebbe troppo semplice la riducibilità
  8. Non troveremo ATM non è decidibile, perché è troppo lungo per un compito (metodo diagonale di Cantor)
Cosa * ¬ A E EQ
DFA Chiuso (1.25 [prodotto cartesiano] oppure 1.45 [equivalenza con NFA]) Chiuso (1.47 [equivalenza con NFA]) Chiuso (1.49 [equivalenza con NFA]) Chiuso (1.25 [prodotto cartesiano]) Chiuso (Esercizio 1.14a) sì (4.1): simulando un DFA in una TM si ottiene accept o reject sì (4.4.): marcare gli stati del DFA ricorsivamente sì (4.5): verificare che la differenza simmetrica dei due DFA sia vuota
NFA Chiuso (1.45) Chiuso (1.47) Chiuso (1.49) Chiuso (1.25 [equivalenza con DFA]) Chiuso (Esercizio 1.14b) sì (4.2): convertire un NFA in un DFA e applicare ADFA
REX Chiuso (definizione 1.52) Chiuso (definizione 1.52) Chiuso (definizione 1.52) Chiuso (equivalenza con DFA) Chiuso (equivalenza con DFA) sì (4.3): convertire REX in NDA e applicare ANFA
CFG Chiuso (esercizio 2.16) Chiuso (esercizio 2.16) Chiuso (esercizio 2.16) Non chiuso (esercizio 2.2) Non chiuso (esercizio 2.2) sì (4.7): convertire il CFG in forma normale di Chomsky, elencare le derivazioni e verificare w sì (4.8): marcare i terminali ricorsivamente no (4.8): poiché i CFG non sono chiusi per intersezione e complemento.
PDA
Linguaggi decidibili Chiuso (esercizio 3.15) Chiuso (esercizio 3.15) Chiuso (esercizio 3.15) Chiuso (esercizio 3.15) Chiuso (esercizio 3.15)
TM Chiuso (esercizio 3.16) Chiuso (esercizio 3.16) Chiuso (esercizio 3.16) Chiuso (esercizio 3.16) No (4.11): metodo della diagonale di Cantor No (5.2) No (5.4)

exercise 3.4

Request

Give a formal definition of an enumerator. Consider it to be a type of two-tape Turing machine that uses its second tape as the printer. Include a definition of the enumerated language.

Answer

An enumerator is comparable to a two-tapes Turing machine, where the second tape moves only to the right. As proved by the theorem 3.13 (Sipser), a two-tapes TM is equivalent to a single tape TM, but keep two tapes is more useful for this answer.

We can describe an enumerator as:

En = (Q, Σ, {Γ1, Γ2}, δ, qaccept, qreject)

where δ(qi, a1, a2) = (qj, b1, b2, {L, R}, {R})

Since the printer is a write-only device and it can move only to the right, it's not necessary to specify what is the current character and where the head must be moved. So the final definition of δ is

δ(qi, a1) = (qj, b1, b2, {L, R})

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.

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.