SKEDSOFT

Automata | Comp. Sc. Engg.

DEFINITIONS: Let us consider a finite automata which accepts the language

We see that M moves from q0 to q1, on the occurence of a’s. On seeing ‘b’, M moves from q1 to q2 and continues to be in the state q2 on getting more b’s. Assume that the input string is given by

a m bn ,

then the resulting state is final state and so M accepts a mbn .

Consider the language where the number of b’sand a’s are equal. The FA constructed for L1 differs from that of L2.

For the language there  is not necessity toremember the number of a’s. The following have to be remembered.

  1. Whether the first symbol is ‘b’ (to reject the string)
  2. Whether ‘a’ follows ‘b’ (to reject the string)
  3. Whether ‘a’ follows ‘a’ and ‘b’ follows ‘b’ (to accept the string).

We know that FA has only a finite number of states, M cannot remember the number of a’s in anbn where ‘n’ is larger than the number of states of M. The FA does not accept the sets of the form {a nbn| n ³1}. This is taken care by a “PUSHDOWN AUTOMATA”. Let us illustrate a Pushdown Automata (PDA) model.

Nondeterministic PDA (Definition): An NPDA is defined by the 7-tuple

M = (Q, S,G,d, q , Z, F ) 0

where

Q = Finite set of inter nal states of the con trol unit

S = Input alpha bet

G = Finite set of sym bols called “Stack alphabet”

d : Q ´ (S È{l}) ´ G ® finite sub sets of Q ´ G* is the transition function

q0 = Initial state of the control unit ÎQ

Z = Stack start symbol

F ⊆ Q = Set of Final states.

The arguments of d are the current state of the control unit,  the current input symbol, and the current symbol on the top of the stack. The result is a set of pairs (q, x) where q = next state of the control unit

x = string that is put on top of the stack in place of the single symbol there before.

The ‘stack’ is an additional component available as part of PDA. The ‘stack’ increases its memory. With respect to {a nbn | n ³1}, we can store a’s in the stack. When the symbol ‘b’ is encountered, an ‘a’ from the stack can be removed. If the stack becomes empty on the completion of processing a given string, then the PDA accepts the string.