IB102 – úkol 8, příklad 1 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).
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 −.