IB102 - úkol 9
Odevzdání: 5.12. 2011
Vypracoval (a): UČO: Skupina:
1. [2 body] Mějme následující jazyk:
L = {we {a, b, c, d}* | #aH = 2#b(w) a #a(w) < #c(w)}
Rozhodněte, zdaje tento jazyk bezkontextový, a své rozhodnutí dokažte. (Pro důkaz toho, že je jazyk bezkontextový, stačí sestrojit příslušnou bezkontextovou gramatiku nebo zásobníkový automat.)
IB102 - úkol 9
Odevzdání: 5.12. 2011
Vypracoval (a): UČO: Skupina:
2. [2 body] Mějme gramatiku G = ({S, A, B, C, D}, {a, b}, P, S), kde
P = {   S -> Aa\ BaC,
A -> Sa | AD,
B -+ Sb\b,
C -> CCa | 6,
D aD\bD }.
Převeďte tuto gramatiku do Greibachové normálni formy použitím algoritmů z přednášky.
Poznámka: Nezapomeňte si nejdřív zkontrolovat, zdaje pro použití algoritmů gramatika ve vhodném vstupním tvaru.