IB102 úkol 9, příklad 2 Odevzdání: 26. 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, F}, {a, b, c}, P, S),
P = { S → CB | cab,
A → ε | EbD | aa,
B → A | Cb | b,
C → ε | BbA,
D → aaaD | aaa | ε,
E → aE | bFa | aDF | bDE,
F → bEaa | Fa}.
Pomocí algoritmů z přednášky převeďte gramatiku G na ekvivalentní vlastní gramatiku a následně na
gramatiku v Chomského normální formě. Do řešení uveďte celý postup převodu, zejména následující
mezivýsledky:
a) ke gramatice G ekvivalentní gramatiku G1 bez ε-pravidel (nezapomeňte uvést množinu Nε obsahující
všechny neterminály, které se dají přepsat na ε),
b) ke gramatice G1 ekvivalentní gramatiku G2 bez ε-pravidel a jednoduchých pravidel (uveďte množiny
NX, t.j. množiny všech neterminálů, na které se může X ∈ N přepsat pomocí jednoduchých
pravidel),
c) ke gramatice G2 ekvivalentní vlastní gramatiku G3,
d) ke gramatice G3 ekvivalentní gramatiku G4 v Chomského normální formě (CNF).
Prvním krokem je odstranění ε-pravidel z gramatiky G. Množina neterminálů, které je možné přepsat
na ε, je Nε = {S, A, B, C, D}. Vzhledem k tomu, že S ∈ Nε (gramatika G generuje ε), přidáváme
nový neterminál S a pravidla S → ε | S. Výsledkem algoritmu z přednášky (8. přednáška, slajd 4)
je poté gramatika:
G1 = ({S , S, A, B, C, D, E, F}, {a, b, c}, P1, S ),
P1 = { S → ε | S,
S → CB | C | B | cab,
A → EbD | Eb | aa,
B → A | Cb | b,
C → BbA | bA | Bb | b,
D → aaaD | aaa,
E → aE | bFa | aDF | aF | bDE | bE,
F → bEaa | Fa}.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.
IB102 úkol 9, příklad 2 Odevzdání: 26. 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.
Druhým krokem je odstranění jednoduchých pravidel. Algoritmus z přednášky můžeme použít,
protože gramatika G1 již neobsahuje ε-pravidla. Pro všechny neterminály X ∈ N jsou množiny
neterminálů, na něž lze neterminál X přepsat, následující:
NS = {S , S, C, B, A},
NS = {S, C, B, A},
NA = {A},
NB = {B, A},
NC = {C},
ND = {D},
NE = {E},
NF = {F}.
Výsledkem algoritmu z přednášky (8. přednáška, slajd 8) je poté gramatika:
G2 = ({S , S, A, B, C, D, E, F}, {a, b, c}, P2, S ),
P2 = { S → ε | CB | BbA | bA | Bb | b | Cb | cab | EbD | Eb | aa,
S → CB | BbA | bA | Bb | b | Cb | cab | EbD | Eb | aa,
A → EbD | Eb | aa,
B → EbD | Eb | aa | Cb | b,
C → BbA | bA | Bb | b,
D → aaaD | aaa,
E → aE | bFa | aDF | aF | bDE | bE,
F → bEaa | Fa}.
Třetím krokem je převod gramatiky na vlastní gramatiku. Na to potřebujeme odstranit nepoužitelné
symboly. Začneme odstraněním nenormovaných neterminálů. Iterativně přidáváme do Ni
neterminály, které lze v i krocích přepsat na řetězec terminálů. Výsledkem podle algoritmu z prednášky
(7. prednáška, slajd 11) je množina:
Ne = {S , S, A, B, C, D}.
Neterminály E, F jsou tedy nenormované a z gramatiky je odstraníme. Výsledkem algoritmu z přednášky
(7. přednáška, slajd 14) je poté gramatika:
G3a = ({S , S, A, B, C, D}, {a, b, c}, P3a, S ),
P3a = { S → ε | CB | BbA | bA | Bb | b | Cb | cab | aa,
S → CB | BbA | bA | Bb | b | Cb | cab | aa,
A → aa,
B → aa | Cb | b,
C → BbA | bA | Bb | b,
D → aaaD | aaa}.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.
IB102 úkol 9, příklad 2 Odevzdání: 26. 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.
Dále odstraníme nedosažitelné symboly. Podle algoritmu z přednášky (7. přednáška, slajd 15)
nejprve iterativně do množiny Vi přidáváme symboly (terminály i neterminály), kterých lze v i
krocích z iniciálního neterminálu S dosáhnout. Výsledná množina V2 je tedy:
V2 = {S , C, B, A, a, b, c}.
Nedosažitelné jsou tedy neterminály S, D, a tudíž je z gramatiky odstraníme. Výstupem algoritmu
je poté gramatika:
G3 = ({S , A, B, C}, {a, b, c}, P3, S ),
P3 = { S → ε | CB | BbA | bA | Bb | b | Cb | cab | aa,
A → aa,
B → aa | Cb | b,
C → BbA | bA | Bb | b}.
Posledním krokem je převod gramatiky G3 do Chomského normální formy podle postupu předvedeného
na přednášce (8. přednáška, slajd 4). Jelikož gramatika G3 neobsahuje jednoduchá ani
ε-pravidla, je také necyklická. Navíc neobsahuje ani nepoužitelné symboly, a tedy se jedná o vlastní
gramatiku. Gramatiku G3 tedy můžeme převést do CNF.
Výsledkem tohoto algoritmu je gramatika:
G4 = ({S , A, B, C, bA , ab , a , b , c }, {a, b, c}, P4, S ),
P4 = { S → ε | CB | B bA | b A | Bb | b | Cb | c ab | a a ,
A → a a ,
B → a a | Cb | b,
C → B bA | b A | Bb | b,
bA → b A,
ab → a b ,
a → a,
b → b,
c → c.}.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.