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

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

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

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ý: 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?

Jen ještě podotknu, že jde o přijímání koncovým stavem kde dno zásobníku je vlevo (tedy vrchol vpravo).

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.

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.

Super. Na to už jsem taky přišel, ze tam bude o jedno *b* navíc, to jsem předtím přehlédl. Ještě je tam jedna chyba, a to že zásobník nepřijímá prázdné slovo - tedy jen epsilon. Jinak se mi taky zdá, že je to dobře.