Úkol 2

Bc. Jan Kaláb <xkalab00@stud.fit.vutbr.cz>

Příklad 1

Uvažte jazyk L₁ = {wcⁱ | w ∈ {a, b}* ∧ (#a(w) = i ∨ #b(w) = i)}.

Sestavte gramatiku G₁ takovou, že L(G₁) = L₁.

G₁ = ({S, A, B}, {a, b, c}, P, S)

P:

S → A | B | ε

A → aAc | bA | ε

B → bBc | aB | ε

Algoritmickým postupem převeďte gramatiku G₁ na zásobníkový automat provádějící syntaktickou analýzu zdola nahoru.

M = ({q, r}, {a, b, c}, {S, A, B, a, b, c, #}, δ, q, #, {r})

Reduce:

δ(q, ε, A) = {(q, S)}

δ(q, ε, B) = {(q, S)}

δ(q, ε, bA) = {(q, A)}

δ(q, ε, aAc) = {(q, A)}

δ(q, ε, aB) = {(q, B)}

δ(q, ε, bBc) = {(q, B)}

δ(q, ε, ε) = {(q, A), (q, B)}

Shift:

δ(q, a, ε) = {(q, a)}

δ(q, b, ε) = {(q, b)}

δ(q, c, ε) = {(q, c)}

Accept:

δ(q, ε, S#) = {(r, ε)}

Lze jazyk L₁ přijmout deterministickým zásobníkovým automatem (DZA)? Zdůvodněte své tvrzení (formální důkaz se nepožaduje).

Nelze. Kvůli ∨ v zadání nevíme, zda použít podmínku #a(w) nebo #b(w), a nevíme tedy, zda na zasobníku počítat b nebo a.

Příklad 2

Mějme jazyky L₁ = {aⁱbʲcⁱdʲ | i, j ∈ ℕ} a L₂ = {aⁱbⁱcʲdʲ | i, j ∈ ℕ}.1) 0 ∈ ℕ Pro každý z jazyků L₁ a L₂ dokažte, nebo vyvraťte, zda je bezkontextový.

L₁

Důkaz sporem.

Předpokládejme, že jazyk L₁ je bezkontextový. Pak podle pumping lemmatu pro bezkontextové jazyky existuje konstanta k taková, že je-li z ∈ L₁ a |z| ≥ k, pak lze z napsat ve tvaru: z = uvwxy, vx ≠ ε, |vwx| ≤ k a pro všechna i ≥ 0 je uvⁱwxⁱy ∈ L1.

Zvolíme si z = uᵏvᵏwᵏxᵏyᵏ, |z| > k, i > 1, pak může dojít k následujícímu rozdělení:

vwx = aᵐ, m ≤ k, #a(z) ≠ #c(z)

vwx = aᵐbⁿ, m + n ≤ k, #a(z) ≠ #c(z) ∨ #b(z) ≠ #d(z)

vwx = bᵐ, m ≤ k, #b(z) ≠ #d(z)

vwx = bᵐcⁿ, m + n ≤ k, #a(z) ≠ #c(z) ∨ #b(z) ≠ #d(z)

vwx = cᵐ, m ≤ k, #a(z) ≠ #c(z)

vwx = cᵐdⁿ, m + n ≤ k, #a(z) ≠ #c(z) ∨ #b(z) ≠ #d(z)

vwx = dᵐ, m ≤ k, #b(z) ≠ #d(z)

Ukázali jsme, že nelze najít takové rozdělení, které by splňovalo podmínky pumping lemmatu pro bezkontextový jazyk, což je spor, a jazyk tedy není bezkontextový.

L₂

G = ({A, S, T}, {a, b, c, d}, P, A)

A → ST

S → aSb | ε

T → cTd | ε

K jazyku L₂ lze sestavit bezkontextovou gramatiku, tudíž je bezkontextový.

Příklad 3

Mějme jazyky L₃ ∈ ℒ₃ a L₂ ∈ ℒ₂. Dokažte, že problém L₂ ⊆? L₃ je (eventuelně není) rozhodnutelný? K důkazu použijte uzávěrové vlastnosti bezkontextový a regulárních jazyků.

L₂ ⊆ L₃ ⇔ L₂ ∩ L₃′ = ∅2) ′ značí doplněk

ℒ₂ jsou uzavřené na průnik s ℒ₃

ℒ₃ jsou uzavřené na doplněk

Problém L₂ ⊆? L₃ je rozhodnutelný.

Příklad 4

Uvažujte jazyk L₄, který je generován gramatikou
G₄ = ({E, T, F}, {(, ), true, or, and, not}, P, E), kde

P:

E → E or T | T

T → T and F | F

F → (E) | not(E) | true

Sestrojte deterministický zásobníkový automat přijímající jazyk L₄ a demonstrujte jeho funkci na přijetí řetězce (true or not(true)) and true.

Deterministický zásobníkový automat přijímající jazyk L4 3) U přechodu ve trvaru a, b / xyz považuji z za nový vrchol zásobníku.

δ(S, (, #)

δ(S, true, ])

δ(Z, or, ])

δ(S, not, ])

δ(N, (, ()

δ(S, true, ))

δ(Z, ), ))

δ(Z, ), ])

δ(F, and, #)

δ(S, true, #)

Příklad 5

Mějme gramatiku G₅ = ({S, A, B, C}, {a, b, c}, P, S), kde

P:

S → aACa

A → B | a

B → C | c

C → Cc | bC | ε

Převeďte gramatiku G5 algoritmicky do Chomského normální formy.

Bez ε přechodů:

Nε⁰ = ∅

Nε¹ = {C}

Nε² = {C, B}

Nε³ = {C, B, A}

Nε⁴ = {C, B, A} = Nε³ = Nε

S → aACa | aAa | aCa | aa

A → B | a

B → C | c

C → Cc | b | bC | c

Bez jednoduchých pravidel:

NS⁰ = {S}

NS¹ = {S} = NS⁰ = NS

NA⁰ = {A}

NA¹ = {A, B}

NA² = {A, B, C}

NA³ = {A, B, C} = NA² = NA

NB⁰ = {B}

NB¹ = {B, C}

NB² = {B, C} = NB¹ = NB

NC⁰ = {C}

NC¹ = {C} = NC⁰ = NC

S → aACa | aAa | aCa | aa

A → Cc | a | b | bC | c

B → Cc | b | bC | c

C → Cc | b | bC | c

Vlastní gramatika (odstranění zbytečných a nedostupných symbolů):

V₀ = {S}

V₁ = {S, a, A, C}

V₂ = {S, a, A, C, c, b}

V₃ = {S, a, A, C, c, b} = V₂ = V

S → aACa | aAa | aCa | aa

A → Cc | a | b | bC | c

C → Cc | b | bC | c

Chomského normální forma:

G = ({S, <ACa>, <Aa>, <Ca>, A, C}, {a, b, c}, P, S)

P:

S → a′<ACa> | a′<Aa> | a′<Ca> | a′a′

<ACa> → A<Ca>

<Aa> → Aa′

<Ca> → Ca′

A → Cc' | a | b | b′C | c

C → Cc' | b | b′C | c

a′ → a

b′ → b

c′ → c

Převeďte gramatiku G5 algoritmicky do Greibachové normální formy.

Vlastní gramatika:

Viz převod do Chomského normální formy

Odstranění levé rekurze (S < A < C):

S → aACa | aAa | aCa | aa

A → Cc | a | b | bC | c

C → b | bC | bC′ | bCC′ | c | cC′

C′ → c | cC′

Greibachové normální forma:

G = ({S, A, C, C′, a′, c′}, {a, b, c}, P, S)

P:

S → aACa′ | aAa′ | aCa′ | aa′

A → a | b | bC | bC′c′ | bCC′c′ | bCc′ | bc′ | c | cC′c′ | cc′

C → b | bC | bC′ | bCC′ | c | cC′

C′ → c | cC′

a′ → a

c′ → c