ZH feladatok megoldásai
A CSOPORT 5. Írja le, hogy milyen szabályokat tartalmazhatnak az egyes Chomskynyelvosztályok (03 típusú nyelvek)! (4 pont) Megoldás: 3. típusú, vagy reguláris nyelvek szabályai
A → aB,
A→a
A, B ∈ N,
a∈T
formájúak, ahol
N nyelvtani (nemterminális) jelek halmaza, T terminálisok halmaza. 2. típusú, vagy környezetfüggetlen nyelvek
A → α, formájú szabályokat tartalmazhatnak, ahol
A ∈ N,
α ∈ (T ∪ N )∗ ,
azaz α tetsz®leges (beleértve a 0-t is), véges számú nyelvtani és terminális szimbólum sorozata. 1. típusú, vagy környezetfügg® (esetleg hosszúság-nemcsökkent®) nyelvek
βAγ → βαγ formájú szabályokat tartalmazhatnak, ahol
A ∈ N,
α, β, γ ∈ (T ∪ N )∗ 1
Ezzel ekvivalens de níció:
α→β alakú szabályok, ahol
|α| ≤ |β|, azaz β hossza nem kisebb α hosszánál. 0. típusú nyelvek szabályaira nincs megkötés. 6. Alakítsa determinisztikussá a következ® véges, nemdeterminisztikus automatát, majd minimalizálja az így kapott determinisztikus automatát!
M1 = h{S, A, B, C, D}, {a, b}, δ, S, {C, D}i, ahol
δ(S, a) = A; δ(S, b) = B; δ(A, a) = B | C; δ(A, b) = C | D; δ(B, a) = C; δ(B, b) = C; δ(C, a) = A; δ(C, b) = B; δ(D, a) = C; δ(D, b) = A. (13 pont) Megoldás: A feladat két részfeladatból tev®dik össze. El®ször determinisztikussá alakítjuk az adott automatát, majd ez utóbbit minimalizáljuk, ha lehet. Determinisztikussá tétel: De niálunk egy új automatát, melynek állapotai a nemdeterminisztikus automata állapotainak részhalmazai, a kiinduló állapot az eredeti kiinduló állapotot tartalmazó halmaz, elfodadó állapotao pedig azok az állapothalmazok lesznek, melyek tartalmazzák az eredeti automata valamely elfogadó állapotát, jelen esetben C -t vagy D-t. Az új automata állapotai és mozgásai szabályai a következ®k:
p0 := {S} kiindulási állapot;
δ(p0 , a) = {A} =: p1 hiszen az eredeti automata S -b®l az a szimbólum hatására az A állapotba megy át. Az így kapott halmaz még nem szerepelt a determinisztikus automata állapotai között, ezért de niálunk egy ilyen új állapotot, p1 -et.
δ(p0 , b) = {B} =: p2
hasonló megfontolások miatt.
δ(p1 , a) = {B, C} =: p3 A p1 állapotból a szimbólum hatására két állapotátmenet adott a kiindulási automatában, ezért p3 állapothalmaz az eredeti automata két állapotát tartalmazza. Ezt az algoritmust követve addig megyünk míg új állapotokat találunk. A továbbiakban csak a mozgási szabályokat szabályokat adjuk meg magyarázat nélkül, ahol az aláhúzott állapotok az els® el®fordulások:
δ(p1 , b) = {C, D} =: p4 δ(p2 , a) = {C} =: p5 δ(p2 , b) = {C} = p5 δ(p3 , a) = {A, C} =: p6 δ(p3 , b) = {B, C} = p3 δ(p4 , a) = {A, C} = p6 δ(p4 , b) = {A, B} =: p7 δ(p5 , a) = {A} = p1 δ(p5 , b) = {B} = p2 δ(p6 , a) = {A, B, C} =: p8 δ(p6 , b) = {B, C, D} =: p9 δ(p7 , a) = {B, C} = p3 δ(p7 , b) = {C, D} = p4 δ(p8 , a) = {A, B, C} = p8 δ(p8 , b) = {B, C, D} = p9 δ(p9 , a) = {A, C} = p6 δ(p9 , b) = {A, B, C} = p8 Elfogadó állapot lesz p3 , p4 , p5 , p6 , p8 , p9 . Ezzel de niáltuk a determinisztikus automatát, hiszen az összes állapotszimbólum párra megadtuk az állapotátmenetet. Minimalizálás: Osztályozást végzünk a determinisztikus automata állapotain egy ún. ekvivalencia-reláció segítségével. A relációt úgy de niáljuk, hogy azok az állapotok legyenek relációban egymással, amelyeket tetsz®leges
jelsorozattal nem tudunk megkülönböztetni egymástól, azaz ezen jelsorozatokat az automata mindig vagy elfogadja, vagy elutasítja bármely egymásssal relációban lév® állapotokból kiindulva. Mivel ez a reláció ekvivalencia-reláció, ezért osztályozást generál az állapotokon. Az egyes ekvivalencia-osztályokat egy iteratív algoritmussal határozzuk meg az alábbiak szerint. Ekvivalenciaosztályokat-családot gyártunk, úgy hogy az egyes ekvivalencia osztályokba az i hosszúságú szimbólumsorozatokkal megkülönböztethetelen állapotok kerüljenek. A 0-dik ekvivalencia osztályba a 0 hosszúságú sorozatokkal megkülönböztethetelen állapotok kerülnek, ezek nyilván az elutasító, és elfogadó állapotok lesznek: 0-ekvivalencia osztályok
{p0 , p1 , p2 , p7 },
{p3 , p4 , p5 , p6 , p8 , p9 }
Az 1-ekvivalencia osztályokat a fentiekb®l úgy kapjuk meg, hogy megnézzük, hogy vannak-e olyan szimbólumok, amikkel meg lehet az egy osztályba tartozó állapotokat különböztetni, azaz hogy bizonyos állapotokból különböz® (el®z® szinten lév®) ekvivalencia-osztályokban lév® állapotba kerülünke. Itt pl. p0 -ból a és b hatására is bent maradunk a {p0 , p1 , p2 , p7 } halmazba, viszont p1 , p2 , p7 -b®l kiindulva mindenképpen {p3 , p4 , p5 , p6 , p8 , p9 } halmazbeli állapotba kerülünk. Hasonló gondolatmenettel az alábbi ekvivalenciaosztályokat kaphatjuk: 1-ekvivalencia-osztályok
{p0 },
{p1 , p2 , p7 },
{p4 },
{p5 },
{p3 , p6 , p8 , p9 }
2-ekvivalencia-osztályok
{p0 },
{p1 , p7 },
{p2 },
{p4 },
{p5 },
{p3 , p6 , p8 , p9 }
azaz a kiindulási determinisztikus automatának 10 állapotából egy 6 állapotot tartalmazó minimálautomatát tudunk létrehozni. 7. Határozza meg az alábbi (véges) automata által felismert nyelvet:
M2 = h{q0 , q1 , q2 }, {a, b}, δ, q0 , {q0 , q1 }i, ahol
δ(q0 , a) = q1 ; δ(q0 , b) = q0 ; δ(q1 , a) = q1 ; δ(q1 , b) = q2 ; δ(q2 , a) = q2 ; δ(q2 , b) = q2 .
(5 pont) Megoldás: Ha felrajzoljuk az automata gráfját nyilvánvaló lesz, hogy a q2 -es állapot csapda, azaz egy szót akkor fogad el az automata, ha nem kerül bele a q2 állapotba. A másik két állapot elfogadó állapot. Az automata a
L(M2 ) = b∗ a∗ nyelvet fogadja el, azaz azt, ahol tetsz®leges hosszú (beleértve a 0-t is) b-kb®l álló sorozatot tetsz®leges hosszú (beleértve a 0-t is) a-kból álló sorozat követ. Ennek természetesen eleme az üres szó is (ε). Más formalizmussal
L(M2 ) = bi aj
i, j ≥ 0.
8. Tekintsük az alábbi környezetfüggetlen grammatikát:
G = h{S, A}, {if, then, else, for, do, a, b, c}, S, {S → if b then A, S → if b then A else S, S → a, A → for c do S, A → a}i. Adjuk meg legbaloldalibb levezetését az if b then for c do if b then a else a jelsorozatnak. Egyértelm¶-e a levezetés, ill. a nyelvtan? (7 pont) Megoldás: Sajnos a feladat eredeti megadása hibás volt. A második szabályban most már az else is szerepel, így az adott mondat levezethet®. A mondat egyik legbaloldalibb levezetési az alábbi (a behelyettesített szimbólum alá van húzva): S → if b then A → if b then for c do S → if b then for c do if b then A else S → if b then for c do if b then a else S → if b then for c do if b then a else A → if b then for c do if b then a else a Hasonlóan helyes legbaloldalibb levezetés azonban az, amikor az elején nem az els®, hanem a második szabályt alkalmazzuk, majd ezt a levezetést foly-
tatjuk:
S → if b then A else S → if b then for c do S else S → if b then for c do if b then A else S → if b then for c do if b then a else S → if b then for c do if b then a else A → if b then for c do if b then a else a
Tehát a levezetés, s így a nyelvtan sem egyértelm¶. 9. Hozza jólfésült nyelvtani formára (proper grammar) az alábbi nyelvtant! Ügyeljen az átalakítások helyes sorrendjére! Hogyan módosítaná a végs® nyelvtant, hogy az üres szó (ε) is eleme legyen a nyelvnek?
S → bB | a | D, B → A | a, A → bE | a, C → c, D → Db, E → a. (10 pont) Megoldás: Jólfésült nyelvtani formára hozás négy egyszer¶ algoritmus alkalmazásából áll: 1. Bottom-up (lentr®l felfelé történ®) sz¶rés 2. Top-down (fentr®l lefelé történ®) sz¶rés 3. ε-mentesítés 4. Egyszeres szabályok kiiktatása Mint az els® pillanatra látható, a nyelvtan nem tartalmaz ε-szabályokat, ezért a 3. algoritmust nem kell végrehajtani a megadott nyelvtanon. Helyette van példában a második kérdés feltéve, tehát, hogyan tudjuk ε-osítani a végs® nyelvtant, ami lényegesen egyszer¶bb feladat, mint az ε-mentesítés. 1. Bottom-up sz¶rés: Az ismert algoritmus alapján az alábbi halmazsorozatot hozzuk létre:
B0 = {a, b, c} B1 = {a, b, c, S, A, B, C, E} =: B
Tehát D nyelvtani szimbólum, és az összes ®t tartalmazó szabályt elhagyható, mivel nem vezethet® le bel®le terminális jelsorozat, így az alábbi szabályok maradnak:
S → bB | a, B → A | a, A → bE | a, C → c, E → a. Megjegyzés: itt D ún. álrekurzíót okozó jel. 2. Top-down sz¶rés:
T0 T1 T2 T3
= {S} = {S, B, a, b} = {S, A, B, a, b} = {S, A, B, E, a, b} =: T
Tehát C nyelvtani, és c terminális szimbólum nem érhet® el a mondatszimbólumból, így marad:
S → bB | a, B → A | a, A → bE | a, E → a. 3. Egyszeres szabályok kiiktatása: egy darab egyszeres szabály maradt:
B→A A top-down sz¶r®algoritmus segítségével az alábbi, az egyes szimbólumokból elérhet® nyelvtani szimbólumokat tartalmazó halmazokat hozzuk létre:
TB = {B, A},
TA = {A},
ami persze els® ránézésre is nyilvánvaló. Ezért a B → A szabályban az A szimbólumot a bel®le kiinduló szabályok jobboldalával helyettesítve az alábbiakat kapjuk: B → bE | a Tehát a jólfésült nyelvtanunk az alábbi szabályokból áll:
S → bB | a, B → bE | a, E → a, hiszen az A nyelvtani jel feleslegessé vált. 4. ε-osítás: bevezetünk egy új Sˆ-sel jelölt mondatszimbólumot, valamint az alábbi szabályokat adjuk a grammatikához:
Sˆ → ε,
Sˆ → S.
B CSOPORT 5. De niálja, mit tekintünk egy Σ alfabéta felett reguláriss halmaznak, és adja meg a rajtuk értelmezett szokásos m¶veleteket! (4 pont) Megoldás: Egy Σ alfabéta felett annak összes egy elem¶ részhalmaza reguláris halmaz ({a} reguláris halmaz ∀a ∈ Σ), valamint reguláris halmaz az üres szót {ε}, és az üres halmazt {∅} tartalmazó halmaz is. Regulárist halmazt kapnuk, ha az akábbi m¶veletek alkalmazásával: unió: P + Q, ahol P, Q reguláris halmaz konkatenáció: P Q, ahol P, Q reguláris halmaz tranzitív lezárt: P ∗ , ahol P reguláris halmaz A konkatenáció m¶velete az egymásután-írást jelenti, azaz P és Q halmaz elemeit egymás után írjuk, míg a tranzitív lezárt a halmazt elemeinek önmagával való egymásutáni-írását tartalmazó halmazt adja meg, formálisan: ∗
P =
∞ [
Pi
i=0
6. Alakítsa determinisztikussá a következ® véges, nemdeterminisztikus automatát, majd minimalizálja az így kapott determinisztikus automatát!
M1 = h{q0 , q1 , q2 , q3 , q4 }, {0, 1}, δ, q0 , {q3 , q4 }i, ahol
δ(q0 , 0) = q1 ; δ(q0 , 1) = q2 ; δ(q1 , 0) = q3 | q4 ; δ(q1 , 1) = q2 | q3 ; δ(q2 , 0) = q3 ; δ(q2 , 1) = q3 ; δ(q3 , 0) = q2 ; δ(q3 , 1) = q1 ; δ(q4 , 0) = q3 ; δ(q4 , 1) = q2 . (13 pont) Megoldás: A feladat két részfeladatból tev®dik össze. El®ször determinisztikussá alakítjuk az adott automatát, majd ez utóbbit minimalizáljuk, ha lehet.
Determinisztikussá tétel: De niálunk egy új automatát, melynek állapotai a nemdeterminisztikus automata állapotainak részhalmazai, a kiinduló állapot az eredeti kiinduló állapotot tartalmazó halmaz, elfodadó állapotao pedig azok az állapothalmazok lesznek, melyek tartalmazzák az eredeti automata valamely elfogadó állapotát, jelen esetben q3 -at vagy q4 -et. Az új automata állapotai és mozgásai szabályai a következ®k:
p0 := {q0 } kiindulási állapot;
δ(p0 , 0) = {q1 } =: p1 hiszen az eredeti automata q0 -ból a 0 szimbólum hatására a q1 állapotba megy át. Az így kapott halmaz még nem szerepelt a determinisztikus automata állapotai között, ezért de niálunk egy ilyen új állapotot, p1 -et.
δ(p0 , 1) = {q2 } =: p2 hasonló megfontolások miatt.
δ(p1 , 0) = {q3 , q4 } =: p3 A p1 állapotból 0 szimbólum hatására két állapotátmenet adott a kiindulási automatában, ezért p3 állapothalmaz az eredeti automata két állapotát tartalmazza. Ezt az algoritmust követve addig megyünk míg új állapotokat találunk. A továbbiakban csak a mozgási szabályokat szabályokat adjuk meg magyarázat nélkül, ahol az aláhúzott állapotok az els® el®fordulások:
δ(p1 , 1) = {q2 , q3 } =: p4 δ(p2 , 0) = {q3 } =: p5 δ(p2 , 1) = {q3 } = p5 δ(p3 , 0) = {q2 , q3 } = p4 δ(p3 , 1) = {q1 , q2 } =: p6 δ(p4 , 0) = {q2 , q3 } = p4 δ(p4 , 1) = {q1 , q3 } =: p7 δ(p5 , 0) = {A} = p2 δ(p5 , 1) = {B} = p1 δ(p6 , 0) = {q3 , q4 } = p3 δ(p6 , 1) = {q2 , q3 } = p4
δ(p7 , 0) = {q2 , q3 , q4 } =: p8 δ(p7 , 1) = {q1 , q2 , q3 } =: p9 δ(p8 , 0) = {q2 , q3 } = p4 δ(p8 , 1) = {q1 , q2 , q3 } = p9 δ(p9 , 0) = {q2 , q3 , q4 } = p8 δ(p9 , 1) = {q1 , q2 , q3 } = p9 Elfogadó állapot lesz p3 , p4 , p5 , p7 , p8 , p9 . Ezzel de niáltuk a determinisztikus automatát, hiszen az összes állapotszimbólum párra megadtuk az állapotátmenetet. Minimalizálás: Osztályozást végzünk a determinisztikus automata állapotain egy ún. ekvivalencia-reláció segítségével. A relációt úgy de niáljuk, hogy azok az állapotok legyenek relációban egymással, amelyeket tetsz®leges jelsorozattal nem tudunk megkülönböztetni egymástól, azaz ezen jelsorozatokat az automata mindig vagy elfogadja, vagy elutasítja bármely egymásssal relációban lév® állapotokból kiindulva. Mivel ez a reláció ekvivalencia-reláció, ezért osztályozást generál az állapotokon. Az egyes ekvivalencia-osztályokat egy iteratív algoritmussal határozzuk meg az alábbiak szerint. Ekvivalenciaosztályokat-családot gyártunk, úgy hogy az egyes ekvivalencia osztályokba az i hosszúságú szimbólumsorozatokkal megkülönböztethetelen állapotok kerüljenek. A 0-dik ekvivalencia osztályba a 0 hosszúságú sorozatokkal megkülönböztethetelen állapotok kerülnek, ezek nyilván az elutasító, és elfogadó állapotok lesznek: 0-ekvivalencia osztályok
{p0 , p1 , p2 , p6 },
{p3 , p4 , p5 , p7 , p8 , p9 }
Az 1-ekvivalencia osztályokat a fentiekb®l úgy kapjuk meg, hogy megnézzük, hogy vannak-e olyan szimbólumok, amikkel meg lehet az egy osztályba tartozó állapotokat különböztetni, azaz hogy bizonyos állapotokból különböz® (el®z® szinten lév®) ekvivalencia-osztályokban lév® állapotba kerülünke. Itt pl. p0 -ból 0 és 1 hatására is bent maradunk a {p0 , p1 , p2 , p6 } halmazba, viszont p1 , p2 , p6 -ból kiindulva mindenképpen {p3 , p4 , p5 , p7 , p8 , p9 } halmazbeli állapotba kerülünk. Hasonló gondolatmenettel az alábbi ekvivalenciaosztályokat kaphatjuk:
1-ekvivalencia-osztályok
{p0 },
{p1 , p2 , p6 },
{p3 , p5 },
{p4 , p7 , p8 , p9 }
2-ekvivalencia-osztályok
{p0 },
{p2 },
{p1 , p6 },
{p3 },
{p5 },
{p4 , p7 , p8 , p9 }
Ezen az ekvivalencia-osztályok már tovább nem bonthatók, megkülönböztethetetlen állapotokat tartalmaznak, hiszen pl. p1 -b®l és p6 -ból 0 hatására p3 -ba, 1 hatására p4 állapotba jut az automata. Így a minimálautomatánk 6 állapotot tartalmaz. 7. Határozza meg az alábbi (véges) automata által felismert nyelvet:
M2 = h{S, A, B}, {a, b}, δ, S, {A, B}i, ahol
δ(S, a) = A; δ(S, b) = B; δ(A, a) = S; δ(A, b) = B; δ(B, a) = A; δ(B, b) = S. (5 pont)
Megoldás: Ha felrajzoljuk az automata gráfját láthatjuk, hogy S -b®l és B -b®l két egymásutáni a-ra visszajutunk a kiinduló állapotba, míg S -b®l és A-ból két egymásutáni b-re szintén ez történik. Ezek tehát azok a jelsorozatok, ami után elutasító állapotba kerül az automata. Áltanánosaban fogalmazva az automata olyan jelsorozatokat fogad el, amelyek nem párosszámú, vagyis páratlan számú a-ra vagy b-re végz®dnek, formálisan:
L(M2 ) = {a2i+1 ∪ b2i+1 ∪ wab2i+1 ∪ wba2i+1 },
i ≥ 0; w ∈ {a, b}∗ .
Itt az els® két kifejezés a csak a-kból és b-kb®l álló elfogadott szavakat írja le, még a második kett® azokat amelyek nem homogének. 8. Egyértelm¶-e az alábbi környezetfüggetlen grammatika? Ha nem, adjon meg olyan jelsorozatot, amelyhez két különböz® levezetési fa tartozik!
G = h{S, A}, {a, b}, S, {S → A, A → AbA, A → a}i.
(7 pont) Megoldás: Sajnos ez a feladat némileg hibás volt, az utolsó szabály helyesen: A → a. Tekintsük az alábbi mondatot: ababa. Ehhez két legbaloldalibb levezetés is tartozik, tehát a mondatnak nincs egyértelm¶ szintaxisfája (a behelyettesített szimbólum alá van húzva):
S → AbA → abA → abAbA → ababA → ababa S → AbA → AbAbA → abAbA → ababA → ababa Tehát a nyelvtan nem egyértelm¶. 9. Hozza jólfésült nyelvtani formára (proper grammar) az alábbi nyelvtant! Ügyeljen az átalakítások helyes sorrendjére! Hogyan módosítaná a végs® nyelvtant, hogy az üres szó (ε) is eleme legyen a nyelvnek?
S → aA | b | E, A → B | b, B → aD | a, C → c, D → b, E → Ea. (10 pont) Megoldás: Jólfésült nyelvtani formára hozás négy egyszer¶ algoritmus alkalmazásából áll: 1. Bottom-up (lentr®l felfelé történ®) sz¶rés 2. Top-down (fentr®l lefelé történ®) sz¶rés 3. ε-mentesítés 4. Egyszeres szabályok kiiktatása Mint az els® pillanatra látható, a nyelvtan nem tartalmaz ε-szabályokat, ezért a 3. algoritmust nem kell végrehajtani a megadott nyelvtanon. Helyette van példában a második kérdés feltéve, tehát, hogyan tudjuk ε-osítani a végs® nyelvtant, ami lényegesen egyszer¶bb feladat, mint az ε-mentesítés.
1. Bottom-up sz¶rés: Az ismert algoritmus alapján az alábbi halmazsorozatot hozzuk létre:
B0 = {a, b, c} B1 = {a, b, c, S, A, B, C, D} =: B Tehát E nyelvtani szimbólum, és az összes ®t tartalmazó szabályt elhagyható, mivel nem vezethet® le bel®le terminális jelsorozat, így az alábbi szabályok maradnak:
S → aA | b, A → B | b, B → aD | a, C → c, D → b. Megjegyzés: itt E ún. álrekurzíót okozó jel. 2. Top-down sz¶rés:
T0 T1 T2 T3
= {S} = {S, A, a, b} = {S, A, B, a, b} = {S, A, B, D, a, b} =: T
Tehát C nyelvtani, és c terminális szimbólum nem érhet® el a mondatszimbólumból, így marad:
S → aA | b, A → B | b, B → aD | a, D → b. 3. Egyszeres szabályok kiiktatása: egy darab egyszeres szabály maradt:
A→B A top-down sz¶r®algoritmus segítségével az alábbi, az egyes szimbólumokból elérhet® nyelvtani szimbólumokat tartalmazó halmazokat hozzuk létre:
TA = {A, B},
TB = {B},
ami persze els® ránézésre is nyilvánvaló. Ezért az A → B szabályban a B szimbólumot a bel®le kiinduló szabályok jobboldalával helyettesítve az alábbiakat kapjuk: A → aD | a Tehát a jólfésült nyelvtanunk az alábbi szabályokból áll:
S → aA | b, A → b | aD | a, D → b.
hiszen a B nyelvtani jel feleslegessé vált. 4. ε-osítás: bevezetünk egy új Sˆ-sel jelölt mondatszimbólumot, valamint az alábbi szabályokat adjuk a grammatikához:
Sˆ → ε,
Sˆ → S.
