Tvorba zásobníkového automatu vol. 2
asked 2014-12-09 14:48:32 +0100
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ý ( 2014-12-09 15:56:51 +0100 )editchci 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 ( 2014-12-09 17:23:10 +0100 )editTaky 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ý ( 2014-12-09 17:55:04 +0100 )editViktor 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 ( 2014-12-10 09:32:54 +0100 )editKde 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 ( 2014-12-10 10:01:56 +0100 )editTak si vymyslete pár testovacích slov (včetně mezních případů), a posílejte je do automatu, a kontrolujte, jestli přijme jenom ty co má. Tím zjistíte, v čem je problém. Například ten co máte na obrázku taky neni úplně správně, nepřijme podle mě třeba abb.
Viktor Chlumský ( 2014-12-10 10:45:05 +0100 )editJá mám v zápiscích ze cvičení i stručně doplněný popis přímo tohoto příkladu a tak, jak to má @Jan Rubín, mi to přijde téměř ok. Pro řetězec abb automat začne ve stavu q0, nedeterministicky se rozhodne, že se vydá do stavu q2 a poté pro každé "a" z řetězce přidá na zásobník dva symboly A (v tomto případě tedy bude zásobník vypadat AA#). S prvním "b" přejde do stavu r a postupně symboly A ze zásobníku odebere (pro každé "b" jedno). Pouze bych upravil ten konec a způsob přijímaní - tak, jak je to napsané tady, potřebuje automat pro přechod do koncového stavu ještě jedno "b" navíc, které už v řetězci není (=nemá tam co dělat). Lepší by byl přechod delta(r, eps, #) = (r, eps), kdy na konci řetězce automat odebere i počáteční symbol a přijme řetězec prázdným zásobníkem.
Zdeněk Kasner ( 2014-12-10 14:53:26 +0100 )edit