Uživatelské nástroje

Nástroje pro tento web


pitel:tin:ukoly:2010:2

Úkol 2

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

Příklad 1

Navrhněte algoritmus, který pro daný netereminál A a bezkontextovou gramatiku G = (N, Σ, P, S) rozhodne, zda A je prvním symbolem nějaké větné formy G, t.j., zda S ⇒* , kde γ ∈ (ΣN)*. Uvědomte si, že některé neterminály mohou být přepsány na ε.

Vstup: G = (N, Σ, P, S); AN
Výstup: Boolean (✔✘)

  1. A = S: ✔
  2. Sestrojíme množinu E, která bude obsahovat neterminály, které se přímo přepisují na ε.
  3. Hledáme v P pravidla tvaru XE* a všechna taková X přidáme do E. Opakujeme, dokud se E mění.
  4. Hledáme v P pravidla tvaru XE*A(NΣ)* a ze všch takových X uděláme množinu T. Tanto krok opakujeme, ale místo A dosazujeme neterminály z T, a stále rozšiřujeme množinu T, dokud můžeme.
  5. Množina T obsahuje počáteční symbol S. ✔

Příklad 2

Nalezněte bezkontextovou gramatiku G s co nejméně pravidly takovou, že pokud v algoritmu 4.3 z přednášky pro odstranění zbytečných symbolů nejdříve provedeme body 3 a 4 (algoritmus 4.2 aplikujeme přímo na G a odstraníme nedostupné symboly) a na výslednou gramatiku aplikujeme body 1 a 2 (odstraníme neterminály jež negenerují žádné věty), dostaneme gramatiku obsahující nedostupný symbol.

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

  • ABC | a
  • Bb
  • CcC

Příklad 3

Gramatiku G = ({A, B, C}, (a, b, c}, P, A) s pravidly

  • ABa | a
  • BBbC | C
  • CCc | A

převeďte algoritmicky do Greibachové normální formy a Chomského normální formy.

Greibachové normální forma

  1. Ostranění ε-pravidel: žádné nejsou.
  2. Odstranění levé rekurze:
    • Aa | aA′
    • A′a | C′a | B′a | C′B′a | aA′ | C′aA′ | B′aA′ | C′B′aA′
    • BC | CB′
    • B′bC | bCB′
    • CA | AC′
    • C′c | cC′
  3. Relace uspořádání: A′ < C′ < B′ < B < C < A
  4. Dosazení v pořadí inverzním k relaci uspořádání:
    • Aa | aA′
    • Ca | aA′ | aC′ | aA′C′
    • Ba | aA′ | aC′ | aA′C′ | aB′ | aA′B′ | aC′B′ | aA′C′B′
    • B′bC | bCB′
    • C′c | cC′
    • A′a | ca | cC′a | bCa | bCB′a | cB′a | cC′B′a | aA′ | caA′ | cC′aA′ | bCaA′ | bCB′aA′ | cB′aA′ | cC′B′aA′
  5. Upravíme pravidla do greibachové normální formy:
    • Aa | aA′
    • Ca | aA′ | aC′ | aA′C′
    • Ba | aA′ | aC′ | aA′C′ | aB′ | aA′B′ | aC′B′ | aA′C′B′
    • B′bC | bCB′
    • C′c | cC′
    • A′a | cA″ | cC′A″ | bCA″ | bCB′A″ | cB′A″ | cC′B′A″ | aA′ | cA″A′ | cC′A″A′ | bCA″A′ | bCB′A″A′ | cB′A″A′ | cC′B′A″A′
    • A″a

Chomského normální forma

  1. Vlastní gramatika: zadaná gramatika už vlastní je.
  2. Bez jednoduchých pravidel:
    • NA = {A}
    • NB = {A, B, C}
    • NC = {A, C}
    • ABa | a
    • BBbC | Cc | Ba | a
    • CCc | Ba | a
  3. Chomského normální forma
    • ABa′ | a
    • BB<bc> | Cc′ | Ba′ | a
    • CCc′ | Ba′ | a
    • a′a
    • c′c
    • <bc>b′C
    • b′b

Příklad 4

Navrhněte deterministický zásobníkový automat přijímající jazyk L z příkladu 6. Přechodovou funkci znázorněte graficky. Automat může mít maximálně 4 zásobníkové symboly a 4 stavy. Demonstrujte přijetí slova abba.

M = ({I, II, III}, {a, b}, {A, B, #}, δ, I, #, {})

Čtený symbol Zásobník1) Přechodová funkce
#
a #A
b #
b #B
a #

Příklad 5

Operátor paralelní kompozice (tzv. shuffle) || : Σ* × Σ* → 2Σ* je definován induktivně tak, že w || ε = ε || w = {w} a aw1 || bw2 = {a} · (w1 || bw2) ∪ {b} · (aw1 || w2). Dále, pro jazyky L1 a L2, L1 || L2 = ∪w1 ∈ L1, w2 ∈ L2. Například {aa}||{bb} = {aabb, abab, abba, baab, baba, bbaa}. Dokažte, že množina bezkontextových jazyků není uzavřena na ||. Postupujte podobně, jako v důkazu neuzavřenosti vůči průniku, t.j., zvolte si dva bezkontextové jazyky L1, L2 a dokažte pomocí pumping lemmatu, že L1 || L2 není bezkontextový.

  • L1 = {anbn | n ≥ 0}
  • L2 = {0m1m | m ≥ 0}
  • L = L1 || L2 = {w | #a = #b ∧ #0 = #1}

Předpokládejme, že L je bezkontextový jazyk.

  • k: zL ∧ |z| ≥ k
  • z = ak0kbk1k, |z| = 4kk
  • uvwxy, vxε, |vwx| ≤ k
  • i = 2

Takto mohou vzniknout řetězce ve tvaru aa…aa00…00bb…bb11…11. Počet opakování jednotlivých symbolů bude k, a pak pro libovolný výběr vwx takový, že |vwx| ≤ k a „napumpování“ dojde vždy k narušení stejného počtu symbolů.

Z výše uvedeného tvrzení plyne, že jazyk L není bezkontextový, a tudíž množina bezkontextových jazyků není uavřena na ||.

Příklad 6

Nechť L je jazyk všech slov nad abecedou {a, b} se stejným počtem výskytů symbolu a jako výskytů symbolu b. Mějme gramatiku G = (S, {a, b}, P, S) s pravidly

  • SaSbS | bSaS | ε

Je gramatika jednoznačná? Dokažte.

Není. Řetězec abab lze vygenerovat dvěma stromy.

Dokažte indukcí k délce slova, že L(G) ⊆ L.

  1. wL(G): |w| = 0 → wL
  2. i = 2
    Z jazyka L můžeme udělat pouze tyto řetězce délky i: ab, ba. Zcela stejn řetězce můžeme vygenerovat i z jazyka L(G) a také to budou jediné možné řetězce o délce i, protože gramatika G vždy generuje stejný počet symbolů a jako b.
  3. Výše uvedené tvrzení platí i pro všechna následující i + 2. (Vygenerované řetězce budou samozřejmě odpovídat patřičné délce i.)

Nechť pro i ∈ ℕ, Li = {w ∈ L | |w| ≤ i}. Dokažte indukcí k i, že Li ⊆ L(G) pro všechna i ∈ ℕ (a tedy L ⊆ L(G)).

Nápověda:

  1. Nejprve zdůvodněte následující tvrzení: Nechť slovo wL \ {ε} má tu vlastnost, že žádný jeho vlastní prefix vyjma ε nepatří do L. Potom w je tvaru aub, nebo bua, kde uL.
  2. Pomocí tvrzení z bodu 1. ukažte, že každé slovo wL \ {ε} lze napsat ve tvaru aubv, nebo buav, kde u, vL.
  3. Tvrzení z bodu 2. použijte v indukčním kroce.

FIXME

1)
Po provedení přechodu
/var/www/wiki/data/pages/pitel/tin/ukoly/2010/2.txt · Poslední úprava: 30. 12. 2022, 13.43:01 autor: 127.0.0.1