Tvorba zásobníkového automatu vol. 2

asked 2014-12-09 14:48:32 +0100

Jan Rubín gravatar image

updated 2014-12-09 21:14:19 +0100

shejby gravatar image

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.

edit retag flag offensive close delete

Comments

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

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 ( 2014-12-09 17:23:10 +0100 )edit

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ý ( 2014-12-09 17:55:04 +0100 )edit

Viktor Chlumský: Já se snažím postupovat analogicky s příkladem, který jsme dělali na cvičení: http://i.imgur.com/xV8ixup.jpg
Kde tedy dělám chybu?

Jan Rubín ( 2014-12-10 09:32:54 +0100 )edit

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

Tak 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 )edit

Já 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