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