IB102 úkol 10, příklad 2 Odevzdání: 3. 12. 2018
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
2. [2 body] Nechť A = ({0, 1, 2, 3, 4, 5}, {a, b, c}, {A, Z}, δ, 0, Z, {5}) je zásobníkový automat, kde
δ(0, a, Z) = {(1, Z)}
δ(0, b, Z) = {(2, Z)}
δ(0, a, A) = {(1, A)}
δ(0, b, A) = {(2, A)}
δ(1, a, Z) = {(0, A)}
δ(1, a, A) = {(0, AA)}
δ(2, a, Z) = {(3, Z)}
δ(2, a, A) = {(3, A)}
δ(3, a, Z) = {(4, Z)}
δ(3, a, A) = {(4, A)}
δ(4, c, Z) = {(5, Z)}
δ(4, c, A) = {(5, A)}
δ(5, c, A) = {(5, ε)}.
Určete, jaký jazyk akceptuje automat A
a) prázdným zásobníkem (Lε(A)),
b) koncovým stavem (L(A)).
Při analýze automatu A si nejprve všimneme, že z jediného koncového stavu 5 neexistuje přechod
do jiného stavu a zároveň je tento stav jediným stavem, ve kterém je možné ze zásobníku mazat. To
znamená, že jazyky Lε a L budou velice podobné, budou se primárně lišit ve tvaru sufixu slov, a to
v počtu znaků c, jelikož je tato „umazávající“ smyčka v 5 právě pod c.
a) Zároveň nám smyčka v 5 říká něco o tom, jak generované slovo w ∈ Lε začíná. Protože umíme
mazat jenom pokud je na vrcholu zásobníku uloženo A a na zásobník přidávají tento symbol právě
přechody pod a, slovo bude muset obsahovat znak a. Dokonce víme, že slovo w bude muset na a
začínat, protože všechny přechody z 0 pod b vedou do stavu 2, kde již není možno na zásobník
přidávat žádné symboly.
Slovo w tedy začíná na a. Jelikož na zásobníku je na začátku Z, přechod je dán deterministicky
do stavu 1. V 1 můžeme číst jenom a a s uloženým Z opět přecházíme do 0, přitom Z přepisujeme
na A.
Slovo w teď nutně začíná na aa. V 0 nyní už můžeme číst b, protože na zásobníku máme umazatelné
A. Pokud ale načteme znovu a, po přesunutí do 1 nám jediný přechod pod a přidává na
zásobník další A a vrací se opět do 0, z čehož se dá usoudit, že na začátku w bude vždy sudý
počet a.
Přechodem z 0 pod b s vrcholem A se dostaneme do 2, ve kterém je možné načíst jenom a
přechodem do stavu 3, kde nás další a přesune do stavu 4. V 4 je možné načíst jenom c.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.
IB102 úkol 10, příklad 2 Odevzdání: 3. 12. 2018
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
Slovo w tedy má prefix a2nbaac pro nějaké n ∈ N, n > 0. I když jsme v koncovém stavu, stále
nemůžeme akceptovat, protože akceptujeme prázdným zásobníkem, ale zásobník prázdný není
(na zásobníku v této chvíli musí být neprázdná sekvence A, zatím jsme žádné neumazali).
V 5 existuje jediný přechod, a to ten, který jsme analyzovali již na začátku. Každým načtením
c umažeme jedno A ze zásobníku. Pro každou dvojici a jsme přidali právě jedno A a dvojic je
n. Pro úplné vyprázdnění zásobníku musíme tedy načíst n znaků c, poté akceptujeme prázdným
zásobníkem.
Tedy Lε(A) = {a2n · baac · cn | n > 0}.
b) Rozdíl oproti předchozímu případu je v tom, že slovo může skončit a být akceptované jakmile
jsme v akceptujícím stavu (5), nemusí obsahovat dostatek c na vyprázdnění zásobníku. Každým
načtením c však musíme umazat A ze zásobníku, t.j. pro načtení jednoho c musí na zásobníku
existovat aspoň jedno A a proto jich můžeme načíst nejvýše tolik, kolik dvojic a načtených dříve.
Dále již nevyžadujeme, aby na vrcholu zásobníku byl při prvním přechodu do 5 znak A. Z toho
plyne, že znak b můžeme načíst hned jako první, tedy existuje cesta do 5 s vrcholem zásobníku
Z. Tato cesta je dokonce stejná jak pro vrchol Z tak pro vrchol A (t.j. nezáleží na tom, jestli
jsme začali b nebo dvojicemi znaků a tak, jak jsme to dělali v předchozím případe).
Celkem dostáváme L(A) = {a2n · baac · cm | 0 ≤ m ≤ n}.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.