Kalábovi

Kalábovic wikina

Uživatelské nástroje

Nástroje pro tento web


pitel:tin:ukoly:2011:2

Úkol 2

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

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:

  • SA | B | ε
  • AaAc | bA | ε
  • BbBc | 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), (q, S)}

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) 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 zL₁ a |z| ≥ k, pak lze z napsat ve tvaru: z = uvwxy, vxε, |vwx| ≤ k a pro všechna i ≥ 0 je uvⁱwxⁱyL1.

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ᵐ, mk, #a(z) ≠ #c(z)
  • vwx = aᵐbⁿ, m + nk, #a(z) ≠ #c(z) ∨ #b(z) ≠ #d(z)
  • vwx = bᵐ, mk, #b(z) ≠ #d(z)
  • vwx = bᵐcⁿ, m + nk, #a(z) ≠ #c(z) ∨ #b(z) ≠ #d(z)
  • vwx = cᵐ, mk, #a(z) ≠ #c(z)
  • vwx = cᵐdⁿ, m + nk, #a(z) ≠ #c(z) ∨ #b(z) ≠ #d(z)
  • vwx = dᵐ, mk, #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)

  • AST
  • SaSb | ε
  • TcTd | ε

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ů.

  • Platí definice podmnožiny: L₂ ⊆ L₃ ⇔ L₂ ∩ L₃′ = ∅2)
  • ℒ₃ jsou na doplněk uzavřené
  • ℒ₂ jsou uzavřené na průnik s ℒ₃
  • Problém se tedy redukoval na prázdnost ℒ₂, a ten je rozhodnutelný.
  • Problém L₂ ⊆? L₃ je tady také 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:

  • EE or T | T
  • TT 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 L43)

  1. δ(S, (, #)
  2. δ(S, true, ])
  3. δ(Z, or, ])
  4. δ(S, not, ])
  5. δ(N, (, ()
  6. δ(S, true, ))
  7. δ(Z, ), ))
  8. δ(Z, ), ])
  9. δ(F, and, #)
  10. δ(S, true, #)

Příklad 5

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

P:

  • SaACa
  • AB | a
  • BC | c
  • CCc | bC | ε

Převeďte gramatiku Galgoritmicky 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ε
  • SaACa | aAa | aCa | aa
  • AB | a
  • BC | c
  • CCc | 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
  • SaACa | aAa | aCa | aa
  • ACc | a | b | bC | c
  • BCc | b | bC | c
  • CCc | 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
  • SaACa | aAa | aCa | aa
  • ACc | a | b | bC | c
  • CCc | b | bC | c

Chomského normální forma:

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

P:

  • Sa′<ACa> | a′<Aa> | a′<Ca> | aa
  • <ACa> → A<Ca>
  • <Aa> → Aa
  • <Ca> → Ca
  • ACc' | a | b | bC | c
  • CCc' | b | bC | c
  • a′ → a
  • b′ → b
  • c′ → c

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

Vlastní gramatika:

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

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

  • SaACa | aAa | aCa | aa
  • ACc | a | b | bC | c
  • Cb | 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:

  • SaACa′ | aAa′ | aCa′ | aa
  • Aa | b | bC | bCc′ | bCCc′ | bCc′ | bc′ | c | cCc′ | cc
  • Cb | bC | bC′ | bCC′ | c | cC
  • C′ → c | cC
  • a′ → a
  • c′ → c
1)
0 ∈ ℕ
2)
′ značí doplněk
3)
U přechodu ve trvaru a, b / xyz považuji z za nový vrchol zásobníku.
/var/www/wiki/data/pages/pitel/tin/ukoly/2011/2.txt · Poslední úprava: 03. 07. 2012, 13.53:39 autor: 127.0.0.1