– Semester finals – pushdown automaton T_T

530 views
0

Hey fellows, first post kind of ever on Reddit. Can anyone explain pushdown automatons? Its a concept of “formal languages” and the automatons recognizing them….kinda… 😀
Sorry im not really sure about the terminology in English. Help me please! Also, any related material is welcome to be explained like I am five.

In: Technology

I know what you talk about but don’t know where to start exactly.

For example do you know the turing machine already?

Can help you in german or english, maybe pm me?

>Can anyone explain pushdown automatons

It’ll help to know how far into computational theory you are.

A pushdown automaton is essentially a finite state machine (FSM) that has a stack.

You have a bunch of states, and rules on how you move between states depending on what letters appear in the string you’re testing. Some states are “good” states, where you want to stop in, and some are “bad” states, where you don’t want to stop.

A Pushdown automaton (PA) can, in addition to moving between states, push a symbol on to the stack, remove symbols from the stack, and can have rules that say “You can only move from this state to that state if the next letter is ‘1’ and the top symbol on the stack is ‘A'” or “You can always move to this state whenever the stack is empty”

A PA can be used to recognize all deterministic Context-free languages. a PA is more powerful than a finite state machine, but less powerful than a turing machine.