Domácí úkol č. 5
Příklad 1 (5 bodů)
Sestrojte zásobníkový automat akceptující jazyk
L = {ak
bl
cm
dn
| k, l, m, n ∈ N0 ∧ k = m + l + n}
Příklad 2 (5 bodů)
Sestrojte zásobníkový automat akceptující jazyk
L = {u.c.v | u, v ∈ {a, b}∗
, |u| = |v|}
Příklad 3 (5 bodů)
Mějme bezkontextovou gramatiku G = ({S, A, B}, {a, b}, P, S), kde množina
pravidel P je definována takto:
S → aB | bA
A → bAA | aS | a
B → aBB | bS | b
Zkonstruujte zásobníkový automat M pro nedeterministickou syntaktickou analýzu
shora dolů. Následně zapište akceptující výpočet na slově abbaaabb.
Příklad 4 (5 bodů)
Mějme bezkontextovou gramatiku G = ({S, A, B}, {a, b}, P, S), kde množina
pravidel P je definována takto:
S → cS | aAB | aB
A → aAB | aB
B → bB | b
Zkonstruujte zásobníkový automat M pro nedeterministickou syntaktickou analýzu
zdola nahoru. Následně zapište akceptující výpočet na slově caabbb.
1