DHARMNON-REGULAR GRAMMARS 293
l For string ∈(∈(∈)):
S ⇒ S(S) ⇒ S(S(S)) ⇒ S(S(∈)) ⇒ S(∈(∈)) ⇒∈(∈(∈))
Here we again reach to a unique derivation tree.
And similarly test for other strings of L(G). We find that the above case is true for all of
its strings. Hence, CFG G is an unambiguous grammar.
Note → By careful observation of above examples we find that in a grammar, from start-
ing symbol S if two are more intermediate productions reaches on the same string then gram-
mar may be an ambiguous grammar.
Let G has productions S → A1 | A2 ...... | Ak
where A1 ⇒N x (∈ VT*)
and A2 ⇒N x (∈ VT*)
then G is ambiguous.
11.8 Pushdown Automaton.....................................................................................................
Pushdown automaton (PDA) is an extended finite state automaton model of computation such
that it recognizes the context free languages (CFLs). The abstract machine model of the PDA
is shown in Fig. 11.19 essentially has an input tape, a finite control, and additionally a stack
(FILO) of infinite length whose bottom boundary is known but no top boundary.
a bbb...TMZ 0:::Hq 0 Finite ControlFig. 11.19
The stack contains a string of symbols from some alphabets. The leftmost symbol of the
stack is considered to be at the top of the stack. Assume Γ is the finite set of stack symbols
whose first element is Z 0. The automaton will be deterministic, having some finite number of
possible transitions in each situation. Let Q be the set of states. Tape T consists of input alpha-
bets from the set of input alphabets Σ. Initially (t = 0) assume that automaton is in state q 0 and
the stack pointer points to the stack start symbol Z 0. Tape cells are scanned by the read only
tape head H which move right on each scan of the cell and never returns back.
PDA follows two types of moves. In the first type of move, an input symbol is used.
Depending upon the input symbol, the top stack symbol, and the state of the automaton, sev-
eral transitions are possible. These transitions consist of a next state from the set Q and a
possible string of symbols (possibly empty) to replace (push/pop) the top stack symbol then
tape head move one cell right. The second type of move is similar to the first, except that the