IB102 – úkol 6, příklad 2 – řešení Odevzdání: 27. 10. 2014
Vypracoval(a): UČO:
Skupina:
2. [2 body] Uvažte následující gramatiku G:
G = ({S, A, B, C, D}, {a, b, #}, P, S)
P = {S → BSD | ASB | #,
A → a | b,
B → Aa | Ab,
C → aB | bB,
D → Ca | Cb}
Popište jazyk generovaný touto gramatikou, rozhodněte, zda je gramatika jednoznačná
a zda je jazyk generovaný touto gramatikou jednoznačný. Svá rozhodnutí zdůvodněte.
Jazyk generovaný gramatikou je
L(G) = {u#v | u, v ∈ {a, b}∗
, |v| = 2|u|}.
Aby gramatika byla jednoznačná, musel by existovat pro každé slovo generované gramatikou
jediný derivační strom. Uvážíme-li ale například slovo aa#aaaa ∈ L(G), pak
možný derivační strom je
S
D
aC
B
aA
a
a
S
#
B
aA
a
nebo
S
B
aA
a
S
B
aA
a
S
#
A
a
A
a
Gramatika tedy jednoznačná není.
Jazyk generovaný touto gramatikou jednoznačný je, neboť existuje jednoznačná gramatika,
která jej generuje. Můžeme vzít například následující gramatiku G , pro kterou
platí L(G) = L(G ):
G = ({S , A , B }, {a, b, #}, P , S )
P = {S → A S B | #,
A → a | b,
B → A a | A b}.
IB102 – úkol 6, příklad 2 – řešení Odevzdání: 27. 10. 2014
Vypracoval(a): UČO:
Skupina:
Každé slovo z jazyka L(G) má délku 3k + 1 pro nějaké k ≥ 0. Pro libovolné k tedy
musíme přesně k-krát přepsat kořenový neterminál pomocí pravidla S → A S B (zřejmě,
neterminál A se vždy přepíše na právě jeden znak, a tedy je nutné nagenerovat přesně k
neterminálů A ).
Přepis neterminálů A , B se řídí vždy znakem, který je ve slově na daném místě. Opět
tedy nemáme při generování žádného slova možnost volby.