Ask Your Question
0

Zásobníkový automat - koncový stav

asked 2014-12-09 16:29:34 +0100

uchytmat gravatar image

updated 2014-12-09 16:34:52 +0100

Ahoj, Jakým způsobem se má formálně zapsat v sedmici definující zásobníkový automat to, že přijímající stav je stav kdy je prázdný zásobník?

např.: ZA = (q, {a, b}, {S, A}, \delta, q, S, -- koncový stav - zasobnik prazdny --)

Díky

edit retag flag offensive close delete

3 Answers

Sort by » oldest newest most voted
0

answered 2014-12-09 16:51:21 +0100

Viktor Chlumský gravatar image

Buď můžete udělat prázdnou množinu koncových stavů, z toho to tak nějak logicky vyplývá, protože jinak by nepřijímal nic. Kombinovat obojí stejně nesmíte (např. přijímám pokud je prázdný zásobník nebo jsem v koncovém stavu).

Nebo to v tý písemce klidně napište slovně, ale nepleťte tam moc ty pojmy, v tomhle kontextu je termín stav pevně definovaný - je to jedno to kolečko v tom diagramu. Takže stačí třeba "Jazyk je přijímán prázdným zásobníkem."

Jinak oficiální zápis můžete vidět v přednášce 7, slída 5:

$L_{\varepsilon}(R) = L$

edit flag offensive delete publish link more

Comments

Kombinovat se sice nesmi (pokud se nesmi), nicmene mi nic nebrani v tom, abych pridal pravidlo: Pokud jsem v koncovem stavu, vyprazdni zasobnik. Pokud mam prazdny zasobnik, prejdi do koncoveho stavu. Neboli je jedno jestli prijimam koncovym stavem nebo prazdnym zasobnikem.

Jasmes ( 2014-12-10 10:03:19 +0100 )edit

Vážně? Takový přechod, který kontroluje jestli je prázdný zásobník bych chtěl vidět. Ale ano, samozřejmě to je vzájemně převoditelné.

Viktor Chlumský ( 2014-12-10 10:23:40 +0100 )edit

Primo z prednasek z AAG: δ(q, ε, SZ) = {(p, ε)} Syntaxe mi uz trosku vypadava, ale udelat prechod jsem ve stavu Q, na vstupu mam EOF, na zasobniku # (pocatecni symbol) -> prejdi do koncoveho stavu P by nemelo byt nemozne, ne?

Jasmes ( 2014-12-10 10:40:49 +0100 )edit

Pokud prázdným zásobníkem myslíte ve skutečnosti to, že je na vrcholu symbol, který jste tam dal na začátku a od té doby se s ním určitě nemanipulovalo, tak to samozřejmě ano. Jen pozor na to, že zkontrolovat, že je doopravdy úplně prázdný, přímo nejde, a stejně tak ani to, že je celý vstup už přečtený (žádný EOF tu neexistuje, ale taky se to dá vyřešit jinak).

Viktor Chlumský ( 2014-12-10 10:53:37 +0100 )edit

Tim EOF jsem myslel nejakou zarazku, kterou si pridam na konec slova. Nemuzu preci rict, ze jsem prijal dane slovo, dokud nezkontroluji, ze jsem precetl cely vstup.

Jasmes ( 2014-12-10 12:13:54 +0100 )edit
0

answered 2014-12-09 16:35:31 +0100

hajekvo2 gravatar image

My jsme to na cvičení, tuším, psali jako prázdnou množinu, tedy:

ZA = (q, {a, b}, {S, A}, \delta, q, S, {})

edit flag offensive delete publish link more
0

answered 2014-12-09 16:50:05 +0100

United121 gravatar image

My jsem to na cviceni psali uplne bez toho (divny) ....

a v prednaskach je myslim prazdna mnozina - takovy preskrtly kolecko

edit flag offensive delete publish link more

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
1 follower

Stats

Asked: 2014-12-09 16:29:34 +0100

Seen: 229 times

Last updated: Dec 09 '14