Bc. Jan Kaláb <[email protected]>

Popište pomocí kompozitního diagramu jednopáskový Turingův stroj M, který provádí sčítání dvou čísel ve dvojkové soustavě. Pokud bude vstupní kofigurace pásky ΔA#BΔ^ω, kde A, B ∈ {0, 1}⁺, tak stroj zastaví normálně a na pásce bude po zastavení konfigurace Δ*ΔCΔ^ω, kde C = A + B (ve dvojkové soustavě). Pokud bude na vstupu jiný, než povolený řetězec, tak chování stroje není stanovené.

Viz přiložený kompozitní diagram.

Dvojzásobníkový automat D definujeme jako n-tici D = (Q, Σ, Γ, δ, q₀, Z₀, F), kde

• Q, Σ, Γ, q₀, F mají stejný význam jako v definici zásobníkového automatu,
• Z₀ ∈ Γ je startovací symbol obou zásobníků,
• δ je přechodová funkce ve tvaru δ: Q × (Σ ∪ ε) × Γ × Γ → 2^{(Q × Γ* × Γ*)}

Konfigurace, přechod a jazyk přijímaný dvojzásobníkovým automatem jsou definovány obdobně jako u zásobníkových automatů.

Popište ideu důkazu (podobně jako je tomu u vět 7.2 a 7.3 v přednáškách), že třída jazyků přijímaných dvojzásobníkovými automaty je ekvivalentní třídě jazyků přijímaných Turingovými stroji. Uvažujte pouze dvojzásobníkové automaty přijímající přechodem do akceptačního stavu.

Pozn.: Nezapomeňte, že v důkazu ekvivalence je třeba dokázat oba směry.

Aby byla třída jazyků dvojzásobníkové automatu ekvivalentní třídě jazyků Turingových strojů, musí být dvojzásobníkové automaty schopny provádět stejné operace jako Turingovy stroje. Tedy posun na pásce vlevo, vpravo, čtení a zápis.

Nejdříve ukážeme implementaci pásky pomocí dvou zásobníků. Čtecí hlavu představuje vrchol prvního zásobníku. Obsah páský nalevo od čtecí hlavy pak představuje zbytek prvního zásobníku, obsah pásky napravo pak celý obsah druhého zásobníku.

Nyní můžeme přistoupit k popisu implementace jednotlivých funkci Turingova stroje pomocí dvojzásobníkového automatu:

• Posun hlavy vlevo: vyjmeme symbolu z prvního zásobníku a vložíme jej na druhý zásobník
• Posun hlavy vpravo: vyjmeme symbol z druhého zásobníku a vložíme jej na první zásobník
• Čtení: vyjmeme symbol z prvního zásobníku a opět ho vrátíme zpět
• Zápis: vyjmeme symbol z prvního zásobníku, a místo něj vložíme nový

Tím jsme ukázali, že dvojzásobníkový automat má stejnou funkcionalitu jako Turingův stroj. Nyní ještě ukážeme, že pomocí Turingova stroje dokážeme simulovat dvojzásobníkový automat.

Předpokládejme, že páska Turingova stroje ne nekonečná oběma směry. Zapíšeme na pásku nějaký oddělovací symbol ∉ Σ. Obsah pásky nalevo od něj bude představovat první zásobník, obsah pásky napravo od něj pak druhý zásobník. Vložení symbolu na zásobník bude vypadat následovně: Přesuneme hlavu na Δ za koncem řetězce na pásce (levým nebo pravým, podle toho na který zásobník chceme vkládat) a symbol na pásku zapíšeme. Vyjmutí symbolu ze zásobníku bude podobné: Přesuneme hlavu na poslední symbol znak řetězce na pásce (levý nebo pravý, podle toho ze kterého zásobníku chceme číst) a přepíšeme jej na Δ.

Tímto jsme ukázali, že dvojzásobníkový automat dovede simulovat Turingův stroj a naopak, tudíž jsou třídy jejich jazyků ekvivalentní.

Dokažte, že problém, zda jazyk daného TS obsahuje alespoň jedno slovo z jazyka L₃ = {ww | w ∈ {a, b}*} je nerozhodnutelný. Inspirujte se v přednáškách a semináři STI.

Nápověda: Vhodným postupem je redukce jazyka HP na (problém zastavení) na jazyk problému P = {⟨M⟩ | (L(M) ∩ L₃) ≠ ∅}

• Problém HP je charakterizován jazykem HP = {⟨M⟩#⟨w⟩ | M je TS, který na řetězci w zastaví}
• Problém neprázdnosti můžeme charakterizovat jazykem P = {⟨M⟩ | (L(M) ∩ L₃) ≠ ∅}
• Sestrojíme redukci δ: {0, 1, #}* → {0, 1}*, která redukuje HP na P.
• δ přiřadí každému řetězci x ∈ {0, 1, #}* řetězec ⟨Mₓ⟩ ∈ {0, 1}*, kde Mₓ je TS, který se na vstupu w ∈ {0, 1}* chová následovně:
  • Jestliže x nemá strukturu x₁#x₂, kde x₁ je kód TS a x₂ je kód jeho vstupu, ZAMÍTNE
  • Jinak smaže obsah w své vlastní pásky, zapíše na pásku x₁#x₂,
  • následně Mₓ odsimuluje běh TS s kódem x₁ na vstupu s kódem x₂
  • Pokud simulace skončí, přijme, jinak cyklí
• δ je úplná funkce a současně se dá snadno implementovat úplným TS, který vygeneruje M_x realizující výše uvedené kroky a přitom:
  • Kontrola správného formování kódu TS odpovídá testu na členství v regulárním jazyce.
  • Vymazání pásky a zápis konstantního řetězce na pásku je triviální.
  • K simulaci zadaného kódu TS lze užít univerzální TS, který je dostatečně dobře známý.
• Pro jazyk TS Mₓ platí:
  • L(Mₓ) = ∅ právě tehdy, když x nemá strukturu x₁#x₂, kde x₁ je kód nějakého TS a x₂ kód nějakého vstupu, NEBO když simulace TS s kódem x₁ na vstupu s kódem x₂ neskončí.
  • L(Mₓ) = {0, 1}* právě tehdy, když x = x₁#x₂ a x₁ je kód TS, který zastaví na vstupu s kódem x₂.
• δ tedy zachovává členství v jazyce dle definice redukce, neboť:
  ⟨Mₓ⟩ ∈ P ⇔ L(Mₓ) = {0, 1}* ⇔ x = x₁#x₂, kde x₁ je kód TS, který zastaví na vstupu s kódem x₂ ⇔ x ∈ HP

Na obrázku 1 je zobrazen TS M₄.

• Sestrojte gramatiku G₄, takovou, že L(G₄) = L(M₄).
• Pro nějaké slovo w ∈ L(M₄) popište běh stroje M₄ vedoucí k přijetí w a derivaci v gramatice G₄ vedoucí k vytvoření slova w.

G₄ = {{S, F, B}, {a, b}, P, S}

P:

• S → aF
• F → bB | ε
• B → bB | aS

w = abbaa

S ⇒ aF ⇒ abB ⇒ abbB ⇒ abbaS ⇒ abbaaF ⇒ abbaa