[Introduzione alla teoria della computazione] Esercizio 1.10

[FeddyLix17]

Usare la costruzione nella prova del Teorema 1.49 per dare i diagrammi di stato degli NFA che riconoscono lo star dei linguaggi descritti in

1. Esercizio 1.6b


2. Esercizio 1.6j


3. Esercizio 1.6m

Teorema 1.49

La classe dei linguaggi regolari è chiusa rispetto all'operazione star.

IDEA.   Abbiamo un linguaggio regolare A₁, e vogliamo provare che anche A^*₁ è regolare.

Prendiamo un NFA N₁ per A₁ e lo modifichiamo per riconoscere A^*₁, come mostrato nella figura seguente.

L'NFA N risultante accetterà il suo input quando esso può essere diviso in varie parti ed N₁ accetta ogni parte.

Possiamo costruire N come N₁ con ε-archi supplementari che dagli stati accettanti ritornano allo stato iniziale.

In questo modo, quando l'elaborazione giunge alla fine di una parte che N₁ accetta, la macchina N ha la scelta di tornare indietro allo stato iniziale per provare a leggere un'altra parte che N₁ accetta.

Inoltre, dobbiamo modificare N in modo che accetti ε, che è sempre un elemento di A^*₁.

Un'idea (leggermente cattiva) è semplicemente aggiungere lo stato iniziale all'insieme degli stati accettanti.

Questa strategia certamente aggiunge ε al linguaggio riconosciuto, ma può anche aggiungere altre stringhe non volute.

L'esercizio 1.15 chiede un esempio che mostri l'insuccesso di questa idea.

Il modo per correggerla è aggiungere un nuovo stato iniziale, che è anche uno stato accettante, e ha un ε-arco entrante nel vecchio stato iniziale.

Questa soluzione ha l'effetto desiderato di aggiungere ε al linguaggio senza aggiungere qualcos'altro.

DIMOSTRAZIONE

Sia N₁ = (Q₁, Σ, δ₁, q₁, F₁) che riconosce A₁. Costruiamo N = (Q, Σ, δ, q₀, F) per riconoscere A^*₁.

1. Q = { q₀ } ∪ Q₁. Gli stati di N sono gli stati di N₁ più un nuovo stato iniziale.

2. Lo stato q₀ è il nuovo stato iniziale.

3. F = { q₀ } ∪ F₁. Gli stati accettanti sono i vecchi stati accettanti più il nuovo stato iniziale.

4. Definiamo δ in modo che per ogni q ∈ Q e ogni a ∈ Σ_ε,

$$ \Large \delta(q,\ a) = \begin{cases} \delta_1(q,\ a) \quad \quad \quad \quad q \in Q_1\text{e}\ q \notin F_1 \\ \delta_1(q,\ a) \quad \quad \quad \quad q \in F_1\ \text{e}\ a \neq \epsilon \\ \delta_1(q,\ a) \cup \{q_1\} \quad q \in F_1\ \text{e}\ a = \epsilon \\ \{q_1\} \quad \quad \quad \quad \quad \ \ \ q = q_0\ \text{e}\ a = \epsilon \\ \emptyset \quad \quad \quad \quad \quad \quad \ \ \ q = q_0\ \text{e}\ a \neq \epsilon. \end{cases} $$