PUSH DOWN AUTOMATA:

A finite automaton with a data structure which will allow it to recognize strings of the form anbn. To tell if a string is of the form anbn we need to match the a’s with the b’s. We could use a counter for this, but thinking ahead a bit, there is a computer science way to do this. We shall allow the machine to build a pile of discs as it processes the a’s in its input. Then it will unpile these disks as it passes over the b’s.Pushdown automata can be presented as state tables in very much the sameway as finite automata. All we need to add is the ability to place (or push)symbols on top of the stack and to remove (or pop) symbols from the top of the stack. Here is a state table for our machine of figure 1 which accepts strings of the form anbn.

[nggallery id=18]

TURING MACHINE:

A Turing machine is the simplest form of a computer. The concept was invented by Alan Turing in 1936. This was the first computer invented (on paper only).A Turing machine is composed of a “tape”, a ribbon of paper of indefinite length. There is a “head” that can read the symbol, chose to write a new symbol in place, and then move left or right. The Turing machine is said to be in a certain “state”. Finally, the program is a list of “transitions”, that is a list that says, given a current state and a symbol currently under the head, what should be written on the tape, what state the machine should go, and whether the head should move left or right.The tape is used to store data. In addition, it can also store a series of transitions (a small programs) and thus, the head can run “sub-programs”. We then say a Turing machine is emulating another one (the one on the tape).