Settembre 2019 Archive

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.

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

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

Dimostrare che E_DFA è decidibile.

Risposta

Idea: Per dimostrare che E_DFA è 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: E_DFA e EQ_DFA. Bisogna quindi costruire uno dei due:

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

Strada E_DFA

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

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

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

Strada EQ_DFA

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

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

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