Fac simile del compito di calcolabilità e linguaggi formali

Posted by On Filed under 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.