Teoretická informatika - Úkol č.1 Lukáš Sztefek, xsztef01 18. října 2012
Příklad 1 (a) Gramatika G1 je čtveřice G1 = (N, Σ, P, S) kde, • N je konečná množina nonterminálních symbolů N = {A, B, C} • Σ je konečná množina terminálních symbolů Σ = {a, b, c} • P je konečná množina přepisovacích pravidel ( S → AbBC ) A → aAb | P = B → bB | C → bCc | • SN je počáteční symbol gramatiky (b) Gramatika G1 nemůže být podle Chomského chierarchie typu 3, protože obsahuje pravidla ve tvaru A → , tedy generuje prázdný řetězěc. Gramatika je typu 2. Jazyk L1 nemůže být podle Chomského chierarchie typu 3, protože neexistuje takový konečný automat, který by L1 přijal. Existuje však zásobníkový automat, který jazyk příjme, a proto je typu 2. Typ gramatiky a jazyku se obecně lišit mohou. Gramatika typu X může generovat jazyky typu X a vyšších.
Příklad 2 Část (a): 1. Převod RV → RKA M (a) Rozklad zadaného regulárního výrazu vyjádříme stromem:
(b) Převod stromu na konečný automat M : i. Regulárnímu výrazu r7 = b přísluší automat N1 :
2
ii. Regulárnímu výrazu r6 = b∗ přísluší automat N2 :
iii. Regulárnímu výrazu r9 = a přísluší automat N3 : iv. Regulárnímu výrazu r10 = c přísluší automat N4 : v. Regulárnímu výrazu r8 = ac přísluší automat N5 : vi. Automat pro r4 je shodný s automatem pro r5, zkonstruujeme proto rovnou automat N6 = (b∗ + ac):
vii. Regulárnímu výrazu r2 = (b∗ + ac)∗ přísluší automat N7 :
viii. Regulárnímu výrazu r13 = c přísluší automat N8 : ix. Regulárnímu výrazu r12 = a přísluší automat N9 :
x. Regulárnímu výrazu r11 = c∗ přísluší automat N10 : xi. Regulárnímu výrazu r3 = ac∗ přísluší automat N11 :
3
xii. Regulárnímu výrazu r1 = (b∗ + ac)∗ ac∗ přísluší automat N12 :
2. Převod RKA M → DKA M 0 , podle Algoritmu 3.6 z opory předmětu TIN:
7→
J
J J
A = -uz({1}) = {1, 2, 3, 6, 7, 9, 10, 11}
a -uz({4, 17})={4, 12, 13, 15} = B
b -uz({8}) = {2, 3, 6, 7, 8, 9, 10, 11} = C
B = {4, 12, 13, 15}
-uz({∅}) = D
-uz({∅}) = D
-uz({5, 14}) = {2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15} = E
C = {2, 3, 6, 7, 8, 9, 10, 11} D=∅ E = {2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15}
-uz({4, 12}) = {4, 12, 13, 15} = B ∅=D
-uz({∅}) = D
-uz({∅}) = D
∅=D
-uz({4, 12}) = B
-uz({8}) = C
F = {13, 14, 15}
-uz({∅}) = D
-uz({∅}) = D
∅=D -uz({14}) = {13, 14, 15} = F -uz({14}) = {13, 14, 15} = F
4
c -uz({∅}) = D
Grafické znázornění DKA M’:
3. DKA M 0 → redukovaný DKA M 00 , kde L(M 0 ) = L(M 00 ): (a) Automat neobsahuje nedostupné stavy, tudíž není zapotřebí odstraňovat. (b) Automat je úplný, není nutno zůplňovat. (c) Sestrojíme iterativně relaci nerozlišitelnosti stavů: 0
≡
J
a
b
c
B E F
D (II) B (I) D (II)
D (II) C (II) D (II)
E (I) F (I) F (I)
A C D
B (I) B (I) D (II)
C (II) C (II) D (II)
D (II) D (II) D (II)
I
II
5
1
a
b
c
D (IV ) D (IV )
D (IV ) D (IV )
E (III) F (I)
II { A
B (I) B (I)
C (II) C (II)
D (IV ) D (IV )
III { E
B (I)
C (II)
F (I)
IV { D
D (IV )
D (IV )
D (IV )
a
b
c
I{ B
D (V )
D (V )
E (IV )
II { F
D (V )
D (V )
F (II)
n
A C
B (I) B (I)
C (II) C (II)
D (IV ) D (IV )
IV { E
B (I)
C (III)
F (I)
V{ D
D (V )
D (V )
D (V )
≡
J
J
I
n
B F
2
≡
J J
II
J
6
Redukovaný DKA M 00 v grafické podobě (pro přehlednost jsem přejmenoval stavy do tvaru napravo):
7
Část (b): K jednotlivým stavům redukovaného DKA M 00 přiřadíme ekvivalenční třídy. Pro náš automat jich existuje pět: (a) L−1 (A)
(b) L−1 (B)
(c) L−1 (C)
(e) L−1 (E)
(d) L−1 (D)
Cvičně jsem vytvořil ekvivalenční třídu popsanou RV pro (a) L−1 (A) pomocí rovnic s RV. Výsledek L−1 (A) = (b + (ac)+ b)∗ odpovídá příslušnému automatu.
8
Příklad 3 Zadaný KA M3 , který má být převeden na ekvivalentní RV, s pojmenovanými stavy:
Víme, že |X = pX + q nad RV je |X = p∗ q
Soustava rovnic pro M3 : (1) X = aX + aY (2) Y = bZ + cX (3) Z = bX + Řešení soustavy: 1. Dosazení Y do (1): X = aX + a(bZ + cX) X = aX + abZ + acX
(distributivita)
2. Dosazení Z do předchozího výrazu: X = aX + acX + ab(bX + ) X = aX + acX + abbX + ab (distributivita) X = aX + acX + abbX + ab (identita ) X = (a + ac + abb)X + ab (Částečné vytknutí X) 3. Použijeme výše uvedenou rovnici z rámečku a tím získáme výsledný RV ekvivalentní s M3 : X = (a + ac + abb)∗ ab
9
Příklad 4 Vstupní automaty: KA M1 = (Q1 , Σ1 , δ1 , q1 , F1 ) KA M2 = (Q2 , Σ2 , δ2 , q2 , F2 ) Požadovaný výstup: KA M3 takový, že L(M3 ) = {w|w ∈ L(M1 ) ∧ ∃w0 ∈ L(M2 ) : |w| = |w0 |} Definice: M3 = (Q3 , Σ3 , δ3 , q3 , F3 ) kde: • Q3 = Q1 × Q2 • Σ3 = Σ1 • δ3 : q11 , q12 ∈ Q1 , q21 , q22 ∈ Q2 , a ∈ Σ1 : (q12 , q22 ) ∈ δ3 ((q11 , q21 ), a) ⇔ ∃b ∈ Σ2 : q12 ∈ δ1 (q11 , a) ∧ q22 ∈ δ2 (q21 , b) • q3 = (q1 , q2 ) • F3 = F1 × F2
Příklad 5 Zadaný jazyk: L = {w|w ∈ {a, b, c}∗ ∧ #a (w) > #b (w) > #c (w)}, kde #x (w) je počet symbolů x ve slově w. Důkaz sporem: • Předpokládejme, že L ∈ L3 : Pak dle silnější PL platí: ∃k > 0 : ∀w ∈ L : |w| ≥ k → ∃x, y, z ∈ Σ∗ : w = xyz ∧ 0 < |y| ∧ |xy| ≤ k ∧ i ≥ 0 : xy i z ∈ L • Uvážíme libovolné k > 0 takové, že: ∀w ∈ L : |w| ≥ k → ∃x, y, z ∈ Σ∗ : w = xyz ∧ 0 < |y| ∧ |xy| ≤ k ∧ i ≥ 0 : xy i z ∈ L • Zvolme w = ck bk+1 ak+2 ∈ L : |w| = 3k + 3 ≥ k • Z výše uvedeného plyne: ∃x, y, z ∈ Σ∗ : ck bk+1 ak+2 = xyz ∧ 0 < |y| ∧ |xy| ≤ k ∧ i ≥ 0 : xy i z ∈ L • Uvažme libovolné x, y, z ∈ Σ∗ takové, že: ck bk+1 ak+2 = xyz ∧ 0 < |y| ∧ |xy| ≤ k ∧ i ≥ 0 : xy i z ∈ L • Z výše uvedeného plyne, že: xy ∈ {cl |0 < l ≤ k} a současně z = ck−l bk+1 ak+2 • Ovšem zvolíme-li libovolné i > 2k, pak xy i z nebude mít počet symbolů b větší než počet symbolů c. Tedy xy i z ∈ / L, je SPOR. Jazyk L není regulární.
10
Příklad 6 Relace je ekvivalencí, pokud je zároveň reflexivní, symetrická a tranzitivní. Pokud pro relaci nerozlišitelnosti dokážeme 3 tyto vlastnosti, můžeme o ní prohlásit, že jde o ekvivalenci. Definice nerozlišitelnosti: Nechť M = (Q, Σ, δ, q0 , F ) je úplný deterministický KA. Říkame, že řetězec w ∈ Σ∗ nerozlišuje stavy q1 , q2 ∈ Q, když (q1 , w) `∗M (q3 , ) ∧ (q2 , w) `∗M (q4 , ) ∧ (q3 ∈ F ⇔ q4 ∈ F ). Důkaz ekvivalence nerozlišitelnosti: • reflexivní - q ≡ q: q ≡ q : (q, w) `∗M (q3 , ) ∧ (q, w) `∗M (q4 , ) ∧ (q3 ∈ F ⇔ q4 ∈ F ) Pro DKA platí, že se z jednoho stavu dá s jedním konkrétním rětězcem dostat pouze do jednoho stejného stavu. Proto platí: q3 = q4 = q1 a tedy: (q1 ∈ F ⇔ q1 ∈ F ), což je vždy platná formule a relace je proto reflexivní. • symetrická - q1 ≡ q2 → q2 ≡ q1 : Předpoklad q1 ≡ q2 : Využijeme zde komutativity konjunkce a symetrie ekvivalence: (q1 , w) `∗M (q3 , ) ∧ (q2 , w) `∗M (q4 , ) ∧ (q3 ∈ F ⇔ q4 ∈ F ) což lze přepsat do tvaru: (q2 , w) `∗M (q4 , ) ∧ (q1 , w) `∗M (q3 , ) ∧ (q4 ∈ F ⇔ q3 ∈ F ) z čehož plyne: q2 ≡ q1 Relace je tedy symetrická. • tranzitivní - q1 ≡ q3 ∧ q3 ≡ q5 → q1 ≡ q5 což odpovídá výrazu: (q1 , w) `∗M (q2 , ) ∧ (q3 , w) `∗M (q4 , ) ∧ (q2 ∈ F ⇔ q4 ∈ F ) ∧ (q3 , w) `∗M (q4 , ) ∧ (q5 , w) `∗M (q6 , ) ∧ (q4 ∈ F ⇔ q6 ∈ F ) Díky definici tranzitivity ekvivalence platí: (q2 ∈ F ⇔ q4 ∈ F ) ∧ (q4 ∈ F ⇔ q6 ∈ F ) ⇒ (q2 ∈ F ⇔ q6 ∈ F ) Protože musí být všechny části konjunkce platné, musí být platné i výrazy: (q1 , w) `∗M (q2 , ) ∧ (q5 , w) `∗M (q6 , ) Složením 2 výše zmíněných výrazů dostáváme výraz : (q1 , w) `∗M (q2 , ) ∧ (q5 , w) `∗M (q6 , ) ∧ (q2 ∈ F ⇔ q6 ∈ F ) z čehož plyne: q1 ≡ q5 Relace je tedy tranzitivní. Jelikož je relace nerozlišitelnosti stavu ≡ zároveň reflexivní, symetrická a tranzitivní, je to relace ekvivalence.
11
