Úkol 2

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

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 ⇒* Aγ, kde γ ∈ (Σ ∪ N)*. Uvědomte si, že některé neterminály mohou být přepsány na ε.

Vstup: G = (N, Σ, P, S); A ∈ N
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 X → E* a všechna taková X přidáme do E. Opakujeme, dokud se E mění.
4. Hledáme v P pravidla tvaru X → E*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. ✔
6. ✘

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)

• A → BC | a
• B → b
• C → cC

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

• A → Ba | a
• B → BbC | C
• C → Cc | A

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

1. Ostranění ε-pravidel: žádné nejsou.
2. Odstranění levé rekurze:
   • A → a | aA′
   • A′ → a | C′a | B′a | C′B′a | aA′ | C′aA′ | B′aA′ | C′B′aA′
   • B → C | CB′
   • B′ → bC | bCB′
   • C → A | 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í:
   • A → a | aA′
   • C → a | aA′ | aC′ | aA′C′
   • B → a | 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:
   • A → a | aA′
   • C → a | aA′ | aC′ | aA′C′
   • B → a | 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

1. Vlastní gramatika: zadaná gramatika už vlastní je.
2. Bez jednoduchých pravidel:
   • N_A = {A}
   • N_B = {A, B, C}
   • N_C = {A, C}
   • A → Ba | a
   • B → BbC | Cc | Ba | a
   • C → Cc | Ba | a
3. Chomského normální forma
   • A → Ba′ | a
   • B → B<bc> | Cc′ | Ba′ | a
   • C → Cc′ | Ba′ | a
   • a′ → a
   • c′ → c
   • <bc> → b′C
   • b′ → b

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	#

Operátor paralelní kompozice (tzv. shuffle) || : Σ* × Σ* → 2^Σ* je definován induktivně tak, že w || ε = ε || w = {w} a aw₁ || bw₂ = {a} · (w₁ || bw₂) ∪ {b} · (aw₁ || w₂). Dále, pro jazyky L₁ a L₂, L₁ || L₂ = ∪_{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 L₁, L₂ a dokažte pomocí pumping lemmatu, že L₁ || L₂ není bezkontextový.

• L₁ = {aⁿbⁿ | n ≥ 0}
• L₂ = {0^m1^m | m ≥ 0}
• L = L₁ || L₂ = {w | #_a = #_b ∧ #₀ = #₁}

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

• ∀ k: z ∈ L ∧ |z| ≥ k
• z = a^k0^kb^k1^k, |z| = 4k ≥ k
• ∀ 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 ||.

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

• S → aSbS | bSaS | ε

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

1. ∀ w ∈ L(G): |w| = 0 → w ∈ L
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.)

Nápověda:

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