[Introduzione alla teoria della computazione] Esercizio 1.9

[FeddyLix17]

Usare la costruzione nella prova del Teorema 1.47 per dare i diagrammi di stato degli NFA che riconoscono la concatenazione dei linguaggi descritti negli

1. Esercizi 1.6g e 1.6i


2. Esercizi 1.6b e 1.6m

Teorema 1.47

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

IDEA.   Abbiamo i linguaggi regolari A₁ e A₂, e vogliamo provare che A₁ ∘ A₂ è regolare.

L'idea è prendere due NFA, N₁ ed N₂ per A₁ e A₂, e combinarli in un nuovo NFA N come abbiamo fatto nel caso dell'unione, ma questa volta in un modo diverso, come mostrato nella figura seguente.

Poniamo come stato iniziale di N lo stato iniziale di N₁.

Gli stati accettanti di N₁ hanno degli ulteriori ε-archi che non deterministicamente permettono di diramarsi in N₂ ogni volta che N₁ è in uno stato accettante, indicando che ha trovato un pezzo iniziale dell'input che costituisce una stringa in A₁.

Gli stati accettanti di N sono solo gli stati accettanti di N₂.

Quindi, esso accetta quando l'input può essere diviso in due parti, la prima accettata da N₁ e la seconda da N₂.

Possiamo pensare che N non deterministicamente ipotizza dove effettuare la divisione.

DIMOSTRAZIONE

Sia N₁ = (Q₁, Σ, δ₁, q₁, F₁) che riconosce A₁ ed N₂ = (Q₂, Σ, δ₂, q₂, F₂) che riconosce A₂.

Costruiamo N = (Q, Σ, δ, q₁, F₂) per riconoscere A₁ ∘ A₂.

1. Q = Q₁ ∪ Q₂. Gli stati di N sono tutti gli stati di N₁ ed N₂.

2. Lo stato q₁ è lo stato iniziale di N₁.

3. Gli stati accettanti F₂ sono uguali agli stati accettanti di N₂.

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_2\} \quad q \in F_1\ \text{e}\ a = \epsilon \\ \delta_2(q,\ a) \quad \quad \quad \ \ \ \ q \in Q_2. \end{cases} $$