Ask Your Question
3

Tvorba zásobníkového automatu

asked 2014-12-08 19:42:23 +0100

Jan Rubín gravatar image

updated 2014-12-08 21:40:02 +0100

Ahoj,

poradil by mi někdo, jestli mám tento zásobníkový automat dobře navržený? Dělám ho pomocí přijmutí koncovým stavem a nebyl u zadání výsledek. Zadání:

L = {a^i b^j : i > j >= 0}

Vyšlo mi ZA = ({q,r,f,z},{a,b},{#,A},delta,q,#,{z}), kde delta je:

delta(q,a,#) = (r,#)
delta(r,a,#) = (r,#A)
delta(r,a,A) = (r,AA)
delta(r,b,A) = (f,Eps)
delta(f,b,A) = (f,Eps)
delta(f,b,#) = (z,#)

Rád bych poprosil o kontrolu, zda se takto zásobníkový automat správně zapisuje.

Pokud je ZA vůbec správně, tak bych rád poprosil o nějaké lepší řešení, protože tuším, že toto asi nebude elegantní; popřípadě jaké tam mám chyby, kde byla špatná úvaha apod.

Děkuji mnohokrát za rady a odpovědi.

edit retag flag offensive close delete

Comments

Nemas nahodou v tych prechodoch $ \delta(f,f,A)=(f,\epsilon) $ a $ \delta(f,f,\#)=(z,\#) $ preklep? f nie je z konecnej vstupnej abecedy. Chyba mi tam i prechod, aby si prijmal slovo $ a^i $

Lukas Nagy ( 2014-12-08 21:28:39 +0100 )edit

Překlep jsem tam měl, děkuji. Takhle by to mělo být opravdu tak, jak jsem to myslel.

Jan Rubín ( 2014-12-08 21:37:47 +0100 )edit

2 Answers

Sort by » oldest newest most voted
2

answered 2014-12-08 23:25:56 +0100

Viktor Chlumský gravatar image

updated 2014-12-08 23:30:56 +0100

Správně ten automat neni, místo toho jazyka řeší podle mě spíš $i = j$, a navíc požaduje minimálně 2 znaky $b$. Pravidla 1, 2 a 3 jsou zbytečně složitá (proč vzít něco ze zásobníku a zase to tam vrátit, když ani nerozlišuju co to bylo), navíc pokud by to bylo zapsané takhle, tak se ten zásobník hned na začátku ucpe tou mřížkou, protože vrchol zásobníku je vlevo.

Co se týče zápisu, ten je v podstatě OK, ale zobrazení delta by mělo být na množinu, kvůli nedeterminismu - nejde pak napsat třeba $\delta(q, x, y) = (r, z); \delta(q, x, y) = (s, z)$, to by ta rovnost nedávala smysl.

Nějaké lepší řešení? Co třeba:

$R = (\{q, r\}, \{a, b\}, \{x\}, \delta, q, \varepsilon, \{r\}) $

$\delta(q, a, \varepsilon)= \{ (q, x), (r, \varepsilon) \}$

$\delta(r, b, x)= \{ (r, \varepsilon) \}$

edit flag offensive delete publish link more

Comments

Děkuji mnohokrát. Už je mi to jasnější. :)

Jan Rubín ( 2014-12-09 08:52:31 +0100 )edit
0

answered 2014-12-08 21:47:00 +0100

Lukas Nagy gravatar image

updated 2014-12-08 21:48:30 +0100

Pridal by som tam este prechod $ \delta(r,\epsilon,A)=(z,\epsilon) $ a $ \delta(r,\epsilon,\#)=(z,\epsilon) $ a to by ti malo zabezpecit ze prijmes i $ a^i, i \geq 1 $ ak teda nekecam blbosti, ostatne mi pride spravne :)

edit flag offensive delete publish link more

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

Asked: 2014-12-08 19:42:23 +0100

Seen: 19,210 times

Last updated: Dec 08 '14