IB102 úkol 8, příklad 2 Odevzdání: 19. 11. 2018
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
2. [2 body] Uvažte následující gramatiku G:
G = ({S, A, B, C, D, E}, {a, b, c}, P, S)
P = {S → ε | aE | aaD | aBc | CC,
A → a | aa | aA | aB,
B → aBc | BA | SB,
C → ε | cCC | c | cB,
D → Sb | aaDb,
E → aSb | aD}
Popište jazyk generovaný touto gramatikou a zdůvodněte, proč váš jazyk odpovídá zadané gramatice.
Dále rozhodněte, zda je zadaná gramatika jednoznačná, a toto rozhodnutí dokažte.
Gramatiku G můžeme zjednodušit tak, že nejdříve odstraníme neterminál B, jelikož je nepoužitelný
(nelze z něj nikdy vygenerovat větnou formu bez B, je tedy nenormovaný). Jeho odstraněním získáme
následující gramatiku:
G1 = ({S, A, C, D, E}, {a, b, c}, P1, S)
P1 = {S → ε | aE | aaD | CC,
A → a | aa | aA,
C → ε | cCC | c,
D → Sb | aaDb,
E → aSb | aD}
Nyní vidíme, že neterminál A je nedosažitelný. Jeho odstraněním získáme gramatiku:
G2 = ({S, C, D, E}, {a, b, c}, P2, S)
P2 = {S → ε | aE | aaD | CC,
C → ε | cCC | c,
D → Sb | aaDb,
E → aSb | aD}
Pro další zjednodušení gramatiky budeme postupně substituovat neterminály na pravých stranách
pravidel. Substitucí neterminálu E získáme gramatiku:
G3 = ({S, C, D}, {a, b, c}, P3, S)
P3 = {S → ε | aaSb | aaD | CC,
C → ε | cCC | c,
D → Sb | aaDb}
Po substituci neterminálu D bude gramatika vypadat takto:
G4 = ({S, C}, {a, b, c}, P4, S)
P4 = {S → ε | aaSb | CC,
C → ε | cCC | c}
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.
IB102 úkol 8, příklad 2 Odevzdání: 19. 11. 2018
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
Vidíme, že dokážeme vygenerovat vždy společně dva znaky a na začátku slova a jeden znak b na
konci slova, mezi ně lze přidat libovolný počet znaků c (byť v gramatice G4 neterminály C přidáváme
po dvojicích, každý můžeme libovolně přepsat na c nebo ε). Gramatika G4, která je ekvivalentní s G,
tedy generuje následující jazyk L(G) = L(G4) nad abecedou {a, b, c}:
L(G) = {a2n
cm
bn
| n ≥ 0, m ≥ 0}.
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 ε ∈ L(G), pak možné derivační stromy jsou například
S
ε
nebo
S
C
ε
C
ε
Gramatika tedy jednoznačná není. (Jazyk L(G) ale jednoznačný je, protože pro něj dokážeme najít
jednoznačnou gramatiku, viz níže.)
G5 = ({S, C}, {a, b, c}, P5, S)
P5 = {S → ε | aaSb | C,
C → cC | c}
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.