Dnes chci publikovat obecný algoritmus redukce bezkontextové gramatiky. Je to mimojiné zkoušková úloha předmětu Teoretická informatika na VŠB, přičemž pravděpodobně k ničemu jinému tento postup nepoužijete.
Použité pojmy:
- X je neterminál
- Y je neterminál
- a je terminál
- | je symbol "nebo"
- => je symbol "se přepíše na"
- X => Y | a je pravidlo
Než popíšu svůj postup, dovolím si odkázat na teoretické zdroje: jednak je to přímo prezentace, poté animace redukce a nakonec skripta předmětu (strana 157). Vzhledem k tomu, že je to odtamtud náročné pochopit doporučuji postup níže.
Teoretický postup:
- vznikne pomocná množina T z neterminálních symbolů, ze kterých lze odvodit terminální slovo
- tedy ta písmenka vlevo od šipky, která mají na pravé straně koncový znak (terminál)
- do pomocné množiny T přidáme ty neterminály, které lze přepsat na terminály pomocí již přidaných neterminálů.
- přidávám pouze ta pravidla, ve kterých jsou neterminály samotné s terminály nebo s již přidanými neterminály z množiny T
- takto postupujeme, dokud už není co přidat
- z původního zadání škrtneme ty řádky, které mají na levé straně neterminály, které nejsou v množině T
- z původního zadání škrtneme ta pravidla, která v sobě obsahují odstraněné neterminály
- vznikne pomocná množina D neterminálů, které jsou dosažitelné z počátečního neterminálu (typicky S)
- do pomocné množiny D přidáme ty neterminály, které lze dosáhnout z již přidaných neterminálů
- přepsat výslednou redukovanou gramatiku
Praktický postup:
Zadání příkladu: Stručně, ale přesně popište postup redukce gramatiky a přehledně jej aplikujte na zde uvedenou bezkontextovou gramatiku, kde A1 je počáteční neterminál.
A1 => aA1bA5 | A8A3
A2 => A4A5 | A5bA2
A3 => A3aA8b | A8bA6aA6
A4 => aA2A5 | A5aaA4
A5 => A1aA4 | bA7A2
A6 => baA8a | A11abaA1
A7 => bbA7 | A9bA12
A8 => A2bA11 | ab
A9 => bb | aA12b
A10 => A1abA4 | bA10b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
Krok 1. najít terminály
A8 => ab
A9 => bb
do pomocné množiny si přidám neterminály A8 a A9
T = {A8, A9}
Krok 2.1 dokud přibývají další, tak najít další pravidla, která obsahují samostatné terminály z množiny T. Prohledávám:
A1 => aA1bA5 | A8A3
A2 => A4A5 | A5bA2
A3 => A3aA8b | A8bA6aA6
A4 => aA2A5 | A5aaA4
A5 => A1aA4 | bA7A2
A6 => baA8a | A11abaA1
A7 => bbA7 | A9bA12
A10 => A1abA4 | bA10b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
T = {A8, A9} U {A6, A12}
Krok 2.2 prohledávám:
A1 => aA1bA5 | A8A3
A2 => A4A5 | A5bA2
A3 => A3aA8b | A8bA6aA6
A4 => aA2A5 | A5aaA4
A5 => A1aA4 | bA7A2
A7 => bbA7 | A9bA12
A10 => A1abA4 | bA10b
A11 => A1bbA6 | A3bA8
T = {A6, A8, A9, A12} U {A3, A7}
Krok 2.3 prohledávám
A1 => aA1bA5 | A8A3
A2 => A4A5 | A5bA2
A4 => aA2A5 | A5aaA4
A5 => A1aA4 | bA7A2
A10 => A1abA4 | bA10b
A11 => A1bbA6 | A3bA8
T = {A3, A6, A7, A8, A9, A12} U {A1, A11}
Krok 2.4 prohledávám
A2 => A4A5 | A5bA2
A4 => aA2A5 | A5aaA4
A5 => A1aA4 | bA7A2
A10 => A1abA4 | bA10b
T = {A1, A3, A6, A7, A8, A9, A11, A12} U {}konec prohledávání
Krok 3 vypuštění neterminálních stavů z původního zadaní (A2, A4, A5, A10), zbyde:
A1 => aA1bA5 | A8A3
A3 => A3aA8b | A8bA6aA6
A6 => baA8a | A11abaA1
A7 => bbA7 | A9bA12
A8 => A2bA11 | ab
A9 => bb | aA12b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
Krok 4 vyřazení pravidel, která v sobě obsahují vyřazené neterminály (A2, A4, A5, A10), zbyde:
A1 => A8A3
A3 => A3aA8b | A8bA6aA6
A6 => baA8a | A11abaA1
A7 => bbA7 | A9bA12
A8 => ab
A9 => bb | aA12b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
Krok 5 ověření dosažitelnosti již redukovaných pravidel. Do množiny D vždy patří startovací neterminál
D = {A1}
Krok 6.1 z A1 se dá dostat do A3 a A8, přidám si je do seznamu, zbývá
A3 => A3aA8b | A8bA6aA6
A6 => baA8a | A11abaA1
A7 => bbA7 | A9bA12
A8 => ab
A9 => bb | aA12b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
D = {A1} U {A3, A8}
Krok 6.2 je vhodné postupovat rozborem neterminálu A3, zbývá
A3 => A3aA8b | A8bA6aA6
A6 => baA8a | A11abaA1
A7 => bbA7 | A9bA12
A8 => ab
A9 => bb | aA12b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
D = {A1, A3} U {A8, A6}
Krok 6.3 je vhodné postupovat rozborem neterminálu A6, zbývá
A6 => baA8a | A11abaA1
A7 => bbA7 | A9bA12
A8 => ab
A9 => bb | aA12b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
D = {A1, A3, A6} U {A8, A11}
Krok 6.4 je vhodné postupovat rozborem neterminálu A8, zbývá
A7 => bbA7 | A9bA12
A8 => ab
A9 => bb | aA12b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
D = {A1, A3, A6, A8} U {A11}
Krok 6.5 je vhodné postupovat rozborem neterminálu A11, zbývá
A7 => bbA7 | A9bA12
A9 => bb | aA12b
A11 => A1bbA6 | A3bA8
A12 => aA1bA12a | aA9
D = {A1, A3, A6, A8, A11} U {}
Krok 7 z gramatiky jsme vyřadili pravidla:
A7 => bbA7 | A9bA12
A9 => bb | aA12b
A12 => aA1bA12a | aA9
Krok 7.1 zbývá gramatiku přepsat do redukovaného tvaru, toto je výsledek:
A1 => A8A3
A3 => A3aA8b | A8bA6aA6
A6 => baA8a | A11abaA1
A8 => ab
A11 => A1bbA6 | A3bA8
Tím jsme docílili výsledné redukované gramatiky. Je velmi lehké udělat v tomto postupu chybu, odměnou za splnění je obvykle 8 bodů.
K procvičení zde mám i další příklad, tentokráte popsaný výrazně méně: Zadání:
A => FaG | BA
B => IH | aaI
C => ε | aGD
D => aELI | AAH
E => AGF | AA
F => KC | DJa
G => aaaF | bGa
H => IBa | BIH
I => IaI | DH
J => IH | CKFaE | JH
K => ab | ba
L => bLa | Ka
První pomocná množina:
T = {C, K} U {F, L} U {G} U {A} U {E} U {J} U {} = {A, C, E, F, G, J, K, L}
vyřazeno = {B, D, H, I}
Zbývající gramatika:
A => FaG
C => ε
E => AGF | AA
F => KC
G => aaaF | bGa
J => CKFaE
K => ab | ba
L => bLa | Ka
D = {A} U {F, G} U {K, C} U {} = {A, C, F, G, K}
Výsledek
A => FaG
C => ε
F => KC
G => aaaF | bGa
K => ab | ba
Pokud si nejste postupem jistí, zkuste ještě jednou prostudovat oficiální animaci. Poznámka: Všimněme si, že metoda redukce gramatiky nijak nezajišťuje, že výsledná gramatika je nejmenší možná pro daný jazyk, či něco takového. Je to zde jinak než u konečných automatů; neexistuje totiž algoritmus, který by k dané bezkontextové gramatice zkonstruoval nejmenší s ní ekvivalentní.
Žádné komentáře :
Okomentovat
Dotaz, připomínka, oprava?
(pokud máte problém s vložením příspěvku, vyzkoušejte to v prohlížeči Chrome)