IB102 – úkol 8, příklad 1 – řešení Odevzdání: 30. 11. 2015
Vypracoval(a): UČO:
Skupina:
1. [2 body] Uvažme abecedu Σ = {a, =, +, -} a jazyk L nad touto abecedou reprezentující
sčítání a odečítání unárně zapsaných přirozených čísel bez nuly.
Libovolné n ∈ N reprezentujeme jako posloupnost an
. Tedy například číslo 3 bude
reprezentováno jako aaa.
Slova z jazyka L jsou tvaru
ai1
±1 ai2
±2 · · · ±n−1 ain
= z,
kde n ≥ 1, ±k ∈ {+, -} pro všechna 0 < k < n, il > 0 pro všechna 0 < l ≤ n a z je
posloupnost znaků a reprezentující výsledek operace.
Pro každé 0 < k < n označme jako k aritmetickou operaci odpovídající symbolu ±k.
Tedy pokud ±k je +, pak k je +, naopak pokud ±k je -, pak k je −.1
Označme dále jako
rz celé číslo, které je výsledkem operací reprezentovaných částí slova před symbolem =.
Tedy rz = i1 1 i2 2 · · · n−1 in. Konečně, pokud rz ≥ 0, pak klademe z = arz
. Je-li
naopak rz < 0, klademe z = -a−rz
.
Uveďme konkrétní příklady slov z jazyka (mezery ve slově píšeme jen pro lepší čitelnost,
nepatří mezi terminály):
• aaa = aaa,
• a + aa - a = aa,
• a - a = ,
• a - aaaa + aa = -a.
Sestrojte (obyčejný, nikoli rozšířený) nedeterministický zásobníkový automat akceptující
jazyk L. Jasně uveďte, jakým způsobem váš automat akceptuje (koncovým stavem, prázdným
zásobníkem).
Pro řešení vytvoříme zásobníkový automat akceptující prázdným zásobníkem.
Zásobníkový automat intuitivně funguje tak, že během čtení vstupu si na zásobníku
uchovává dosavadní výsledek. Tedy průběžně zvyšuje či snižuje hodnotu reprezentovanou
zásobníkem o počet přečtených a (podle toho, nacházejí-li se znaky a za + nebo za -).
Hodnotu reprezentovanou zásobníkem pak po přečtení znaku = zkontroluje s řetězcem,
který následuje.
Definujme zásobníkovou abecedu Γ = {⊥, P, N}. Řetězec Pn
na zásobníku nám reprezentuje
hodnotu n, řetězec Nn
nám reprezentuje −n.
Množina stavů je Q = {q+
a , q−
a , q+
, q−
, qc, q=}. Ve stavech q+
a a q−
a kontrolujeme nenulovost
operandů. Stavy q+
a q−
reprezentují stavy, ve kterých čteme znaky a a upravujeme
dosavadní hodnotu na zásobníku podle toho, jestli před znaky a bylo + nebo -. Stav q=
1
Všimněte si rozdílu mezi syntaxí a sémantikou. Symbol + je pouhý prvek z abecedy Σ bez jakéhokoliv
významu. Naproti tomu + je standardní binární funkce, která pro dvě celá čísla vrátí jejich součet.
Analogicky pro - a −.
IB102 – úkol 8, příklad 1 – řešení Odevzdání: 30. 11. 2015
Vypracoval(a): UČO:
Skupina:
slouží po přečtění = ke kontrole znaménka výsledku. Ve stavu qc kontrolujeme správný
počet písmen a.
Hledaný automat A (akceptující prázdným zásobníkem) definujeme jako
A = (Q, Σ, Γ, δ, q+
a , ⊥, ∅),
kde přechodová funkce δ je definována níže. Pro přehlednost jsme rozdělili definici do
skupin podle stavů.
Po přečtení znaku + (nebo před začátkem čtení slova) budeme zvyšovat dosavadní
hodnotu na zásobníku o počet následujících znaků a. Pomocí stavu q+
a pohlídáme, že
přečteme minimálně jedno a. Zbytek čtení je pak realizováno ve stavu q+
.
Obdobně sestrojíme přechody pro stav q−
a .
δ(q+
a , a, ⊥) = {(q+
, P⊥)}
δ(q+
a , a, P) = {(q+
, PP)}
δ(q+
a , a, N) = {(q+
, ε)}
δ(q−
a , a, ⊥) = {(q−
, N⊥)}
δ(q−
a , a, P) = {(q−
, ε)}
δ(q−
a , a, N) = {(q−
, NN)}
Ve stavu q+
zvyšujeme se čtením znaků a počet znaků P na zásobníku, je-li dosavadní
výsledek nezáporný, případně ubíráme počet znaků N, je-li záporný. Po přečtení znaku
operace + (či -) přejdeme do stavu q+
a (q−
a ) pro kontrolu nenulovosti operandů. Se znakem
= přejdeme do stavu q= pro kontrolu správnosti výsledku.
Obdobně sestrojíme přechody pro stav q−
.
δ(q+
, a, ⊥) = {(q+
, P⊥)}
δ(q+
, a, P) = {(q+
, PP)}
δ(q+
, a, N) = {(q+
, ε)}
∀X ∈ Γ : δ(q+
, +, X) = {(q+
a , X)}
∀X ∈ Γ : δ(q+
, -, X) = {(q−
a , X)}
∀X ∈ Γ : δ(q+
, =, X) = {(q=, X)}
δ(q−
, a, ⊥) = {(q−
, N⊥)}
δ(q−
, a, P) = {(q−
, ε)}
δ(q−
, a, N) = {(q+
, NN)}
∀X ∈ Γ : δ(q−
, +, X) = {(q+
a , X)}
∀X ∈ Γ : δ(q−
, -, X) = {(q−
a , X)}
∀X ∈ Γ : δ(q−
, =, X) = {(q=, X)}
IB102 – úkol 8, příklad 1 – řešení Odevzdání: 30. 11. 2015
Vypracoval(a): UČO:
Skupina:
Po přečtení znaku = očekáváme na vstupu znak a nebo -. Je-li na vrcholu zásobníku
P, pak nutně za = následuje znak a (neboť má být kladný výsledek). Se znakem - je
analogicky očekáváno na zásobníku N. Pokud je na vrcholu zásobníku znak ⊥, pak je
výsledek operace nulový, a tedy vstup by měl být pro správně utvořené slovo dočten.
Smažeme tedy zásobník.
δ(q=, ε, ⊥) = {(qc, ε)}
δ(q=, a, P) = {(qc, ε)}
δ(q=, −, N) = {(qc, N)}
Ve stavu qc již stačí zkontrolovat, že sedí počet znaků na zásobníku s počtem znaků
za =.
∀X ∈ {P, N} : δ(qc, a, X) = {(qc, ε)}
δ(qc, ε, ⊥) = {(qc, ε)}