Ha szívesen korrepetálnál, hozd létre magántanár profilodat itt.
Ha diák vagy és korrepetálásra van szükséged, akkor regisztrálj be és írd meg itt, hogy milyen tantárgyban!
Veramutomta megadása?
Márk462
kérdése
353
Sziasztok!
A feladat hogy megkell adni egy veremautomatát. A feldat egyik részéhez sikerült külön felírni a veremautomatát, de a másik részéhez nem. Egybe meg az egészet főleg
Az `a` meg `b` elfogadása lehet jó, de a `c`-t belekavartad, ez pedig elrontja. Nálad bárhol lehet `c` (mert ha `c` jön, maradsz ugyanabban az állapotban). Tehát mondjuk elfogad egy olyat szót, hogy `acaaabc c c b c c b c`, pedig csak olyanokat szabadna elfogadni, mint pl. az `aaaab b bc`.
Az `a^ib^j`-hez nem is kell még verem, 4 állapottal verem nélkül is simán meg lehet csinálni:
// `q_0`: kiinduló állapot, valamint páros darab `a`
`q_0,a -> q_1` // `q_1`: páratlan darab `a`
`q_1,a -> q_0`
`q_0,b -> q_2` // `q_2` így: páros darab `a` után páratlan darab `b`
`q_1,b -> q_3` // `q_3`: páratlan darab `a` után páratlan darab `b`
`q_3,b -> q_2` // `q_2` így: páratlan darab `a` után páros darab `b`
És `q_1` valamint `q_2` az elfogadó állapotok.
A nem 2 darab `c` feltételt könnyű hozzátenni `q_1`-ből és `q_2`-ből induló 3 állapottal, ahhoz se kell verem.
Egyelőre nem tudom, hogy veremmel lehet-e kevesebb állapottal csinálni. (Persze elméletileg a fenti is veremautoma, csak sose olvassa és nem is írja a vermet.)
Egyébként nem értem a feladatkiírásban az `i-j` feltételt. Annak is páratlannak kell lennie? Nem is tud páros lenni, ha `i+j` páratlan. Szóval az valami más lehet ott... de mi?
Módosítva: 4 éve
0
Márk462:
A c-re vonatkozó feltétel az k nemegyenlő 2*|i-j| , szóval az i-j az abszolútértékben van
4 éve0
bongolo{ }
válasza
Veremmel:
Mivel 0 darab `c`-vel is lehet jó a szó, azt hiszem csak nemdeterminisztikusan tudunk a fentinél kevesebb állapotú veremautomatát csinálni. 4 állapottal pl. így: (UPDATE: a következő válaszomban determinisztikus veremautomatás megoldás is van)
// A verem tetején `1` van, amikor `i+j` páratlan, egyébként üres (`Z`)
`q_0,a, Z -> q_0,1` // `q_0`: benne vagyunk az `a^i`-ben
`q_0,a,1 -> q_0,ε` // üres a stack, tehát páros az `i`
`q_0, b, Z -> q_1,1` // `q_1`: benne vagyunk az `a^ib^j`-ben
`q_0,b,1 -> q_1,ε` // üres verem: `i+j` páros
`q_1, b, Z -> q_1,1` // 1: `i+j` páratlan
`q_1, b, 1 -> q_1,ε` // üres: `i+j` páros
`q_0,c,1 -> q_2,1` // `q_2`: volt egy `c` is `a^ib^j` után, `i+j` páratlan volt
`q_1,c,1 -> q_2,1` // ez is ugyanúgy
`q_2,c,1 -> q_2,2` // 2 darab `c` volt
`q_2,c,2 -> q_2,3` // 3 darab `c` volt
`q_2,c,3 -> q_2,3` // sok `c` volt
// Most jönnek a nemdeterminisztikus átmenetek; `q_v` az egyetlen elfogadó állapot:
`q_0,ε,1 -> q_v,ε`
`q_1,ε,1 -> q_v,ε`
`q_2,ε,1 -> q_v,ε`
`q_2,ε,3 -> q_v,ε`
Módosítva: 4 éve
0
Még nem érkezett komment!
bongolo{ }
válasza
Éjfél után nem lett volna szabad ilyeneken tűnődnöm, nem igaz, amit írtam. Lehet determinisztikus veremautomata is, sőt, kevesebb állapot is elég.
Két állapot elegendő: `q_0` az induló állapot és egyben az is, hogy rossz odáig a szó (vagyis hogy `i+j` páros, vagy két `c` van), `q_1` pedig az elfogadó állapot (tehát ott `i+j` páratlan és a `c`-k száma is pont jó).
A verem tetején pedig ezek lehetnek:
`Z`, vagyis üres a verem: Ekkor az `a^i` sorozatban vagyunk
`b`: Ekkor az `a^ib^j` sorozatban vagyunk
`1`: Egy darab `c` volt páratlan hosszú `a^ib^j` után
`2`: Két darab `c` volt páratlan hosszú `a^ib^j` után
`3`: Három vagy több `c` volt páratlan hosszú `a^ib^j` után
Az átmenetek pedig:
`q_0, a, Z -> q_1, ε` // páratlan darab `a`
`q_0, b, Z -> q_1, b` // első `b` páros (pl. nulla) darab `a` után
`q_0, b, b -> q_1, b` // `a^ib^j` (`i+j` páros) után újabb `b`
`q_0, c, 2 -> q_1, 3` // kettő `c` után a harmadik (előtte páratlan hosszú `a^ib^j`)
`q_1, a, Z -> q_0, ε` // páros darab `a` lett
`q_1, b, Z -> q_0, b` // első `b` páratlan darab `a` után
`q_1, b, b -> q_0, b` // páratlan hosszú `a^ib^j` után újabb `b`
`q_1, c, Z -> q_1, 1` // páratlan darab `a` után első `c`
`q_1, c, b -> q_1, 1` // páratlan hosszú `a^ib^j` után első `c`
`q_1, c, 1 -> q_0, 2` // páratlan hosszú `a^ib^j` után második `c`
`q_1, c, 3 -> q_1, 3` // páratlan hosszú `a^ib^j` után sokadik `c`
Ennyi.
Ellenőrizd le te is, hátha kimaradt valamilyen szükséges átmenet...
0
Még nem érkezett komment!
bongolo{ }
válasza
Tehát `a^ib^jc^k` lehet a szó, ahol `i+j` páratlan, `k` pedig nem lehet `2n`, ahol `n=|i-j|`.
Vagyis jó szavak pl ezek: `a`, `a b b`, `a b b c`, `a b b c c c`, stb, de nem jó az `a b b c c`.
`i+j` paritását az állapottal nézzük. (Segítségképpen páratlan a `q` indexe, ha `i+j` páratlan)
A vermen annyi jel van, amennyi `n=|i-j|` értéke. Ha `n=0`, üres a verem. Ha `n=1`, akkor egyetlen `1` van a veremben, ha több, akkor `n`-ek vannak felette. `a` növeli, `b` csökkenti az `n`-et, de mikor negatívvá válna, `b` is növeli.
(Azért kell az `n=1`-et külön nézni, mert amikor `c` csökkenti, ekkor tud nullává válni, és ekkor `k=2n` nem jó, még több `c`-nek is lennie kell a szóban.)
Állapotok:
`q_0`: kezdőállapot
`q_1`: `a^ib^jc^k`, `i+j` páratlan, `k > 2n`, jó szó. Ez a leggyakoribb végállapot.
`q_2`: `a^i` sorozat, `i` páros
`q_3`: `a^i` sorozat, `i` páratlan, jó szó
`q_4`: `a^ib^j` sorozat, `i+j` páros, `i-j` pozitív vagy nulla
`q_5`: `a^ib^j` sorozat, `i+j` páratlan, `i-j` pozitív, jó szó
`q_6`: `a^ib^j` sorozat, `i+j` páros, `i-j` negatív
`q_7`: `a^ib^j` sorozat, `i+j` páratlan, `i-j` negatív, jó szó
`q_8`: `a^ib^jc^k` sorozat, `i+j` páratlan, `k=2n` (itt az index páros, de `i+j` páratlan!)
`q_9`: `a^ib^jc^k` sorozat, `i+j` páratlan, `k < 2n`, jó szó
A páratlan indexű állapotok az elfogadóak.
`c` akkor jöhet, amikor `i+j` páratlan.
Ekkor `n=|i-j|` is páratlan, tehát `n > 0`, vagyis a verem tetején `1`-es vagy `n` van. Azok számát csökkenti a `c`, de csak felezve.
A felezés úgy megy, hogy a vermen `2` jelenti a felet (ami `1`-ből csökkent), illetve `m` jelenti azt a felet, ami `n`-ből csökken.
Az átmenetek:
// az első `a`:
`q_0, a, ε -> q_3, 1` // n=1, páratlan
// vagy jöhet rögtön `b` is:
`q_0, b, ε -> q_7, 1` // n=|-1|, páratlan
// A végén ha már sok `c` van a jó szóban, akármennyi több is jöhet:
`q_1, c, ε -> q_1, ε`
// `a^i`:
`q_2, a, ε -> q_3, n` // n nől, páratlan lesz
`q_3, a, ε -> q_2, n` // n nől, páros lesz
// Ha `a^i` után jön az első `b`:
`q_2, b, n -> q_5, ε` // n csökken, páratlan lesz
`q_3, b, n -> q_4, ε` // n csökken, páros lesz
// `q_2`-nél nem tud `1` lenni a verem tetején...
`q_3, b, 1 -> q_6, ε` // `ab`: n nulla lesz, páros lesz
// sokadik `b`:
`q_4, b, n -> q_5, ε` // n csökken, páratlan lesz
`q_5, b, n -> q_4, ε` // n csökken, páros lesz
`q_4, b, Z -> q_7, 1` // n nulla volt, `|-1|` lesz, `i+j` páratlan lesz
`q_5, b, 1 -> q_4, ε` // `a^ib^i`: n nulla lesz, `i+j` páros lesz
// sokadik `b`, amikor `i-j` már negatív:
`q_6, b, ε -> q_7, n` // n nől, páratlan lesz
`q_7, b, ε -> q_6, n` // n nől, páros lesz
// `a^ib^j` után jönnek `c`-k.
// Első `c` csak páratlan `i+j` (tehát `q_3, q_5, q_7`) esetén jöhet:
`q_3, c, n -> q_9, m` // n féllel csökken
`q_5, c, n -> q_9, m` // n féllel csökken
`q_7, c, n -> q_9, m` // n féllel csökken
`q_3, c, 1 -> q_9, 2` // n 1/2 lesz
`q_5, c, 1 -> q_9, 2` // n 1/2 lesz
`q_7, c, 1 -> q_9, 2` // n 1/2 lesz
// sokadik `c`, de még `k < 2n`:
`q_9, c, m -> q_9, ε` // n féllel csökken
`q_9, c, 2 -> q_8, ε` // n nulla lesz (`k=2n` lett)
`q_8, c, ε -> q_1, ε` // `k > 2n` lett, innentől akárhány `c` lehet.
------------------------------------------------------
Jól ellenőrizd le, hátha elrontottam...