Teoretick´a informatika (TIN) – 2014/2015
´
Ukol
2
(max. zisk 5 bod˚u – 10 bod˚u n´ızˇ e odpov´ıd´a 1 bodu v hodnocen´ı pˇredmˇetu)
1. Gramatiku G = ({S, T, C}, {a, b, c}, P, S), kde
P :
S → Ta | a
T → T bC | C
C → Cc | S
pˇreved’te algoritmicky do (a) Chomsk´eho norm´aln´ı formy a (b) Greibachov´e norm´aln´ı formy.
10 bod˚u
2. Necht’ L = {w ∈ {y, z}∗ | #y (w) = #z (w)}, kde #x (w) je poˇcet v´yskyt˚u symbolu x ve slovˇe w. Mˇejme
gramatiku G = ({X}, {y, z}, P, X) s pravidly
X → | zXyX | yXzX.
(a) Je gramatika jednoznaˇcn´a? Ukaˇzte.
(b) Dokaˇzte indukc´ı k d´elce vˇety, zˇ e L(G) ⊆ L.
10 bod˚u
3. Uvaˇzujte z´asobn´ıkov´y automat A = (Q, Σ, Γ, δ, q0 , Z0 , F ) (podle def. 4.16. ve Studijn´ı opoˇre), jehoˇz kaˇzd´y
v´ypoˇcet (posloupnost provediteln´ych pˇrechod˚u zaˇc´ınaj´ıc´ı poˇca´ teˇcn´ı konfigurac´ı) m´a dvˇe f´aze. V prvn´ı f´azi
automat nikdy neodebere vrchol z´asobn´ıku (obsah z´asobn´ıku α se proveden´ım pˇrechodu zmˇen´ı na α.β, kde
β ∈ Γ∗ ). Ve druh´e f´azi nikdy nepˇrid´a symbol na vrchol z´asobn´ıku (obsah z´asobn´ıku α.Z, kde Z ∈ Γ, se
proveden´ım pˇrechodu zmˇen´ı na α nebo z˚ustane stejn´y, obsah z´asobn´ıku se nemˇen´ı proveden´ım zˇ a´ dn´eho
pˇrechodu). Necht’ LZ (A) ⊆ Γ∗ je jazyk vˇsech moˇzn´ych obsah˚u z´asobn´ıku dosaˇziteln´ych v´ypoˇctem automatu A, t.j., LZ (A) = {α | ∃w∃w0 ∃q : (q0 , w, Z0 ) `∗ (q, w0 , α)}. Necht’ G je bezkontextov´a gramatika.
Navrhnˇete algoritmus, kter´y rozhodne, zda LZ (A) obsahuje nˇejakou vˇetu z L(G).
15 bod˚u
4. Necht’ Σ = {a, b, c, d}. Bin´arn´ı operace s jazyky nad Σ∗ je definov´ana tak, zˇ e pro dva jazyky L1 , L2 ⊆ Σ∗ ,
L1 ⊕ L2 = {w ∈ Σ∗ | ∃u ∈ L1 ∃v ∈ L2 : #a (w) = #a (u)∧#b (w) = #b (u)∧#c (w) = #c (v)∧#d (w) =
#d (v)}. Dokaˇzte, zˇ e mnoˇzina bezkontextov´ych jazyk˚u nen´ı uzavˇrena v˚ucˇ i ⊕. M˚uzˇ ete postupovat tˇreba jako v
d˚ukazu neuzavˇrenosti v˚ucˇ i pr˚uniku, t.j., vhodnˇe si zvolte dva bezkontextov´e jazyky L1 , L2 a dokaˇzte pomoc´ı
pumping lemmatu, zˇ e L1 ⊕ L2 nen´ı bezkontextov´y.
15 bod˚u
Download

Teoretická informatika (TIN) – 2014/2015 ´Ukol 2 (max. zisk 5 bodu