Finite Automata (FA) accept regular languages such as ab* . However, FA do not accept Context-Free Languages such as L1 = { anbn : where n > 0 }. What is interesting about L1 is that it has strings with a number of a's followed by an equal numer of b's. So, machines that will accept strings like ab, aabb, aaabbb, . . . ., (that is, the strings of L1) need to be designed in such a way that a's and b's can be matched in some way. A stack is an interesting data-structure which allows operations such as push and pop and increase or decrease its stored contents in a Last-In-First-Out (LIFO) manner. Therefore, stacks are used for processing Context-Free Languages. Well-known acceptors of Context-Free Languages are Pushdown Automata described in text-books such as [1] Cohen, D., Introduction to Computer Theory, 2nd Edition, New York, NY: John Wiley & Sons, 1997. [2] Lewis, H. R. and Papadimitriou, C. H., Elements of the Theory of Computation, 2nd Edition, New Jersey: Prentice_Hall, 1998.
A similar class of machines called One-Stack Automata are presented below whcih are directly augmented from Non-deterministic FA or Transition Graphs of Cohen (1997). Transition Graphs are NFA with null-transitions. The main motivation for One-Stack Automata is to have some machines which are equivalent to Pushdown Automata.
One-Stack Automata are designed to accept Context Free Languages. For example, { anbn : where n >= 0 } is a Context Free Language (CFL) which can be accepted by a one-stack automaton. A one-stack automaton is represented visually as a finite set of states connected with transitions.
Example 1: A one-stack automaton for { anbn : where n >= 0 }
Suppose a string like aabb is given as an input to the above one-stack automaton. Then, the machine starts at the start state and scans the first a and pushes an a into the stack by taking the transition marked by, a, push a . Then it consumes the next a by taking the same transition marked by a, push a . Next, it consumes the symbol b, by taking the transition marked by b, pop a and poping an a from the stack. Then, it scans the next b by taking the transition marked by b, pop a . Then, it
reaches the final state by taking the transition marked by 
,
pop ∆. At that moment, the stack is empty
and the entire input is consumed and therefore the input aabb is accepted by the machine. The one-stack automaton given above accepts any string with a sequence of a's followed by equal number of b's. That is, strings such as ^. ab, aabb, aaabbb, aaaabbbb,. . . . are accepted by the machine.
A one-stack automaton, abbreviated OSA, is composed of one optional and four required components:
1. Σ : a finite non-empty set of symbols called alphabet from which input strings are formed.
2. S: a finite non-empty set of states including
2a. At least one start state marked by -;
2b. Some (may be none) final states marked by + ;
3. Ω : An optional pushdown STACK, infinite in one direction. Initially, the STACK is empty containing all blanks ( ∆).
4. Г: An optional finite non-empty set of symbols called the STACK SYMBOLS. If the STACK is included then the STACK SYMBOLS are also included.
5. T: A finite set of transitions (edge labels) including:
5a. A finite set of transitions that show
how to go from some states to some others,
based on reading a specified symbol or a substring from input, possibly even the null string .
5b. Some (may be none) special transitions each of which reads a symbol and inserts a symbol onto the top of the STACK.
5c. Some (may be none) special transitions each of which reads a symbol and pops a symbol from the top of the STACK.
5d. Some (may be none) special transitions
each of which examines if the stack is
empty by reading and poping ∆.
An input is accepted by an OSA if all of the following conditions are met simultaneously:
(1) the input is entirely consumed, that is, no other symbols left in the input;
(2) the machine is in a final state;
(3) the stack is empty.
The class of languages accepted by One-Stack Automata is exactly the same as the class of languages accepted by Pushdown Automata (PDA)[1, 2]. That is, One-Stack Automata are equivalent to PDA. However, One-Stack Automata are obtained by directly augmenting Non-deterministic Finite Automata (NFA) by adding a stack and its associated operations [3].
Example 2: A one-stack automaton for { ancbn : where n >= 0 }
Example 3: A one-stack automaton for { anb2n : where n >= 0 }
Example 4: A one-stack automaton for { banbc*abn a: where n >= 0 }
For an animation of a One-Stack Automaton, please visit this site
For animations of Pushdown Automata(PDA), please visit this site or this site or this site or this site
One-Stack Automata are equivalent to Pushdown Automata(PDA). The following definition of PDA is basically taken from Cohen (1997).
Definition of Pushdown Automata
A pushdown automaton (PDA) is a collection of eight things:
An alphabet ∑ of input letters.
An input TAPE (infinite in one direction), which initially contains the input string to be processed followed by an infinite number of blanks, ∆
An alphabet E of STACK characters.
A pushdown STACK (infinite in one direction), which initially contains all blanks, ∆.
One START state that has only out-edges, no in-edges. Can have more than one arc leaving the START state. There are no labels on arcs leaving the START state.
Halt states of two kinds:
1. zero or more ACCEPT states
2. zero or more REJECT states
Each of the Halt states have in-edges but no out-edges.
Finitely many nonbranching PUSH states that introduce characters from E onto the top of the STACK.
Finitely many branching states of two kinds:
1. READ states, which read the next unused letter from TAPE and may have out-edges labeled with letters from ∑ or a blank, ∆. (There is no restriction on duplication of labels and no requirement that there be a label for each letter of ∑, or ∆.)
2. POP states, which read the top character of STACK and may have out-edges labeled with letters of E and the blank character ∆, with no restrictions.
A pushdown automaton for { anbn : where n >= 0 } is given below which is taken from Cohen (1997)
According to Hopcroft et al 2007 [4], a Pushdown Automation (PDA), P, is composed of the following seven components
P = (Q,
∑, Γ, δ, q0,
Z0, F)
The components have the following meanings:
Q: A finite set of states, like the states of a finite automaton.
∑: A finite set of input symbols, also analogous to the corresponding component of a
finite automaton.
Γ:
A finite stack alphabet. This component, which has no finite-automaton analog, is
the set of symbols that we are allowed to push onto the stack.
δ: The transition
function. As for a finite automaton,
δ governs the behavior of the
automaton. Formally, δ takes as
argument a triplet δ(q,
a, X), where :
1.
q is a
state in Q
2.
A is either an input symbol in ∑
or a = ε, the empty string, which is assumed not to be
an input symbol.
3.
X is a stack symbol, that is, a member of Γ.
The output of δ is a finite
set of pairs (p, γ), where p is the new state, and
γ is the string of stack symbols tat
replaces X at the top of the stack. For
instance, if γ = ε, then the stack is
popped, if γ = X, then the stack is
unchanged, and if γ = YZ, then X is replaced by Z, and Y is pushed onto the stack.
q0:
The start state. The PDA is in
this state before making any transitions.
Z0 : The start
symbol. Initially, the PDAs stack consists of one
instance of this symbol, and nothing else.
F: The set of accepting states, or final
states. Hopcroft
et al 2007 [4]
For an animation of Pushdown Automata, using adjusted Hopcroft et al notation [4] please visit this site
For visualization of other Automata, please visit this site
References:
[1] Cohen, D., Introduction to Computer Theory, 2nd Edition, New York, NY: John Wiley & Sons, 1997.
[2] Lewis, H. R., and Papadimitriou, C. H., Elements of the Theory of Computation, 2nd Edition, New Jersey: Prentice_Hall, 1998.
[3] W. A. Woods, Transition network grammars for natural language analysis, Communications of the ACM, v.13 n.10, p.591-606, Oct. 1970
[4] Hopcroft, J., Motwani, R., and Ullman, J. Introduction to Automata Theory, Languages, and Computation, Pearson Education, 2007
[5] Sipser, M., Introduction to the Theory of Computation, 2nd Edition, PWS Publishing, 2006.
You are requested to fill out every field; however, a partially filled out form is also accepted. That is, every field is optional.