IB102 - úkol 8
Odevzdání: 28.11. 2011
Vypracoval (a): Skupina:
UCO:
1. [2 body] Mějme následující jazyk nad abecedou {a,b,c,d}:
L = {anbmcrď | n + m = r + s nebo n = s}
Sestrojte jednoznačnou bezkontextovou gramatiku generující tento jazyk. Stručně zdůvodněte, proč je Vaše gramatika jednoznačná.
(Pokud nevíte, jak sestrojit jednoznačnou gramatiku, zkuste sestrojit alespoň nějakou bezkontextovou gramatiku generující tento jazyk. V tom případě bude Vaše řešení hodnoceno maximálně 1 bodem.)
IB102 - úkol 8
Odevzdání: 28.11. 2011
Vypracoval (a): UČO: Skupina:
2. [2 body] Mějme gramatiku G = ({S, A, B, C, D, E, F}, {a, b, c}, P, S), kde
P = {   S -> A | CD | F,
A —ř BA | CAD,
B b | bb,
C -+ e\CD,
D -> e | D,
E -+ aE\bCb\ cFc,
F ab\ aDaDaS | EC }.
Sestrojte vlastni gramatiku G' bez jednoduchých pravidel takovou, že L(G) = L(G). K jejímu sestrojení použijte algoritmů z přednášky.