IB102 – úkol 6, příklad 2 – řešení Odevzdání: 16. 11. 2015
Vypracoval(a): UČO:
Skupina:
2. [2 body] Uvažte následující gramatiku G:
G = ({S, A, B, C, X}, {a, b}, P, S)
P = {S → aAa | CBBb | X,
A → aA | bB | X,
B → A | Bb,
C → Cb | b | bB,
X → a | b | ε}
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.
Gramatika G generuje jazyk všech slov, která začínají a končí stejným písmenem (a ε),
tedy:
L(G) = {a, b, ε} ∪ {x · w · x | w ∈ {a, b}∗
, x ∈ {a, b}}.
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 bbab ∈ L(G), pak možné
derivační stromy jsou například
S
bB
A
X
a
B
A
X
b
C
b
nebo
S
bB
A
X
a
B
bB
A
X
ε
C
B
A
X
ε
b
Gramatika tedy jednoznačná není.
Jazyk generovaný touto gramatikou je ale regulární, jelikož umíme najít regulární
gramatiku, jenž jej generuje. Takovou gramatikou je například gramatika G , pro kterou
platí L(G) = L(G ):
G = ({S , A , B }, {a, b}, P , S )
P = {S → aA | bB | a | b | ε,
A → a | aA | bA ,
B → b | aB | bB }.
Jelikož každý regulární jazyk je jednoznačný, je i jazyk L(G) jednoznačný.