Tvorba zásobníkového automatu

Question

3

Tvorba zásobníkového automatu

asked Dec 8 '14

Jan Rubín
265 ●9 ●17 ●24

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.

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 (Dec 8 '14)

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

Jan Rubín (Dec 8 '14)

add a comment

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 (Dec 8 '14)
Překlep jsem tam měl, děkuji. Takhle by to mělo být opravdu tak, jak jsem to myslel.
Jan Rubín (Dec 8 '14)

Accepted Answer

2

answered Dec 8 '14

Viktor Chlumský
765 ●14 ●24

updated Dec 8 '14

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) \}$

link

Comments

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

Jan Rubín (Dec 9 '14)

add a comment

Answer 2

0

answered Dec 8 '14

Lukas Nagy

171 ●6 ●9 ●16

updated Dec 8 '14

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 :)

link

add a comment

Tvorba zásobníkového automatu

Comments

2 Answers

Comments

Your answer

Question tools

Stats

Related questions