Tvorba zásobníkového automatu vol. 2
asked Dec 9 '14
Ahoj, mám dotaz na další zásobníkový automat, jestli je správně. Trochu s tím bojuju..
Zadání: L(ZA) = {a^n b^m : n,m >= 0; n = m OR m = 2n}
Moje řešení:
ZA = ( { q0,q1,q2,r,f }, {a,b}, {#,A}, delta, q0, #, {f})
delta(q0,Eps,#) = {(q1,#),(q2,#)}
delta(q1,a,#) = {(q1,#A)}
delta(q1,a,A) = {(q1,AA)}
delta(q1,b,A) = {(r,Eps)}
delta(q2,a,#) = {(q2,#AA)}
delta(q2,a,A) = {(q2,AAA)}
delta(q2,b,A) = {(r,Eps)}
delta(r,b,A) = {(r,Eps)}
delta(r,b,#) = {(f,Eps)}
Je to správně? Už si nevím rady.
Děkuji.
A zkusil jste do toho automatu poslat aspoň jedno jediné slovo? Přečet jste vůbec si to co jsem psal minule? Máte tam prakticky úplně ty samé chyby. Doporučuju vám radši se naučit kontrukci ZA podle gramatiky (top-down / bottom-up).
Viktor Chlumský (Dec 9 '14)chci ze zeptat k bottom-up tvorba ... v prednaskach je napsany ze vrchol zasobniku je vzdy napravo ... ale u nas na cviceni se to delalo klasicky ze je vrchol nalevo ( akorat se treba pravidlo S->aSb prepsalo na bSa ... ) mam se to tedy ucit podle cviceni a nebo podle prednasek a proc se to neuci stejne ... akorat zmatek
United121 (Dec 9 '14)Taky si myslím, že je logičtější neměnit definici zásobníkového automatu a místo toho obrátit ty řetězce. Nevím, proč to v přednáškách je takhle. Pokud bude jasné co tím myslíte tak samozřejmě uznáme obojí.
Viktor Chlumský (Dec 9 '14)Viktor Chlumský: Já se snažím postupovat analogicky s příkladem, který jsme dělali na cvičení: http://i.imgur.com/xV8ixup.jpg
Jan Rubín (Dec 10 '14)Kde tedy dělám chybu?
Jen ještě podotknu, že jde o přijímání koncovým stavem kde dno zásobníku je vlevo (tedy vrchol vpravo).
Jan Rubín (Dec 10 '14)