FoNyVizsga

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

Néhány vizsga kérdés kidolgozása:

20031219

2.

Az L1 és az L2 nyelv közös alfabetaja legyen ∑={a,b,c}.

• Az L1 nyelv mondataiban mindhárom karakter száma páratlan

• L2 pedig a következőképpen definiálható: L2={a^i b^j c^k | i,j,k ≥1 és k=2i+3j }

Készítsen minél egyszerűbb nyelvosztályba tartozó nyelvtant vagy automatát mindkét nyelvre és a két nyelv metszetére!

Megoldások

L1-re van minimál automata:

Ezen a helyen volt linkelve a 20031219_2_L1.GIF nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

L2 nem véges így nincs rá véges automata. De lehet rá CF nyelvtant v. verem automatát
CF nyelvtan:

Ezen a helyen volt linkelve a 20031219_2_L2.GIF nevű kép a régi wiki ezen oldaláról. (Kérlek hozd át ezt a képet ide, különben idővel el fog tűnni a régi wikivel együtt)

Thx to: Taki

L2-re verem automata:

L2: [math]\sum=\{a, b, c\} [/math] Verem automata [math]\sum=\{1, 2, 3, \epsilon, Z_{0}\} [/math]
[math]\delta[/math]- mozgások
[math]\delta(q_{0}, a, Z_{0}) = (q_{1}, 2Z_{0})[/math]
[math]\delta(q_{1}, a, 2) = (q_{1}, 22) [/math]
[math]\delta(q_{1}, b, 2) = (q_{1}, 32) [/math]
[math]\delta(q_{1}, b, 3) = (q_{1}, 33) [/math]
[math]\delta(q_{1}, c, 3) = (q_{1}, 2) [/math]
[math]\delta(q_{1}, c, 2) = (q_{1}, 1) [/math]
[math]\delta(q_{1}, c, 1) = (q_{1}, \epsilon) [/math]
[math]\delta(q_{1}, \epsilon, Z_{0}) = (q_{2}, Z_{0}) [/math]


Elfogadó állapotok:
[math]F=\{q_{2}\}[/math]

Kis magyarázat: Amikor bejön egy 'a', akkor berakunk egy '2'-t a verembe. És ezt folytatjuk amíg nem jön egy 'b'. Aztán '3'-t pakolunk a vermbe. Majd ha jönnek a 'c'-k akkor a verem értékéből levonunk 1-et és vissza rakjuk a vermbe. Ha 1-et olvasunk akkor Epsilont rakunk vissza, ergo semmit :). Akkor fogadunk el, ha Epsilont olvasunk és [math]Z_{0}[/math] van a verem tetején.

Delták jelentése:

DELTA(ÁLLPOTBA_VAGYOK, MITOLVASOK, MIVAN_A_VEREMBEN) = (ÁLLAPOTBA_MEGYEK, MIT_RAKOK_A_VEREMBE) A lényeg a lifo elv, azaz: ha kiveszek vlmit olvasásra azt vissza is kell rakjam majd a verembe. Szóval ha olvastam egy "2"-est és bele akarok rakni egy 3-ast akkor azt úgy kell belerakni, hogy előbb visszarakom a 2-est és csak aztán a 3-ast => Delta(q, 32). Meg kell mindig külön mondani az elfogadó állapotokat, F halmaz elemei.

Néhány FONY kidolgozás és sok értékes információ: SzaMa oldalán -- Ede - 2006.01.02.