6

Pushdown Automata

6.1 BASICS OF PUSHDOWN AUTOMATA

Q. What is Pushdown Automata? Describe the Block diagram or Mechanical diagram of Pushdown Automata. Why is it so named 'Pushdown'?

Ans. Pushdown Automata (PDA) is the machine format of context free language (CFL). It is one type of finite state machine (FSM) which is used to accept only CFLs.

Mechanical diagram:

(a) Input Tape: Input tape contains the input symbols. The tape is divided into a number of squares. Each square contains a single input character. The string placed in the input tape is traversed from left to right. Two end sides of the input string contain infinite number of blank symbol.

(b) Reading Head: The head scans each square in the input tape and reads the input from the tape. The head moves from left to right. The input scanned by the reading head is sent to the finite control of the PDA.

(c) Finite Control: Finite control can be considered as a control unit of a PDA. An automaton always resides in a state. The reading head scans the input from the input tape and sends it to finite control. One two way head is also added with the finite control to the stack top. Depending on the input taken from input tape and input from stack top, finite control decides in which state the PDA will move and which stack symbol it will push to the stack or pop from the stack or do nothing on the stack.

(d) Stack: A stack is a temporary storage of stack symbols. Every move of PDA indicates one of the followings to the stack

(i) One stack symbol may be added to the stack [Push]

(ii) One stack symbol may be deleted from the top of the stack [Pop]

Stack is the component of PDA which differentiates it from finite automata. In stack there is always a symbol z₀ which denotes the bottom of the stack.

Why Pushdown: Push is an operation related to stack. By this operation one symbol is added to the stack top.

In finite automata, states act as a form of primitive memory. States memorize the non-terminals encountered at the time of derivation of a string. Hence only state is suitable for traversing a regular expression as in the case of finite automata. Now lets consider a case of L = {aⁿbⁿ where n≥ 1}. It is not a regular expression but a CFL. Here n is any number. In the string there is equal number of 'a' and 'b'. In the string 'a' will occur before 'b'. In case of traversing aⁿbⁿ, the machine has to remember n number of a's to traverse equal number of 'b'. The 'n' is any number. Therefore, to memorize number of a's in the string the machine requires infinite number of states, i.e. the machine will not be a finite state machine.

To remove this difficulty we need to add an auxiliary memory in the form of stack. For each occurrence of 'a' in the string L one symbol is pushed into the stack. For each occurrence of b (After finishing 'a') one symbol will be popped from the stack. By this process the matching of 'a' and 'b' will be done.

By adding a stack to a finite automata, PDA is generated.

Q. Define PDA in mathematical notation.

Ans. A PDA consists of 7-touple where

Q denotes Finite set of states.

denotes Finite set of input symbols

denotes Finite set of pushdown symbols or stack symbols.

denotes transitional functions.

q₀ is the initial state of PDA [q₀ Q]

z₀ is the stack bottom symbol.

F is the final state of PDA.

In PDA transitional function is in the form

(From one state with an input symbol on the tape and with the stack top symbol, the PDA moves to one right, may change its state, and push some symbol in the stack or pop symbol from the stack top.)

Q. Define Instantaneous Description (ID) in the respect of PDA.

Ans. Instantaneous Description (ID) describes the configuration of PDA at a given instant. Instantaneous Description remembers the information of state and stack content at a given instance of time.

An ID is a format of triple (q,w,k), where q Q (finite set of states), w (Finite set of input alphabets) and (Finite set of stack symbols).

6.2 ACCEPTANCE BY A PDA

Q. What are the conditions to declare a string accepted by PDA?

Ans. There are two ways to declare a string accepted by a PDA (a) Accepted by empty stack (store) (b) Accepted by final state.

(a) Accepted by empty stack (store): We know in each PDA there is a stack attached. In the stack at the bottom there is a symbol called stack bottom symbol. In each move of the PDA one symbol called stack symbol is either pushed in or popped from the stack. But the symbol z₀ still remains in the stack.

A string w may be declared accepted by empty stack after processing all the symbols of w, if the stack is empty after reading the rightmost input character of the string w. In mathematical notation we can say be a PDA, the string w is declared accepted by empty stack if

In general we can say that a string is accepted by a PDA by empty stack if both the following conditions are fulfilled.

(i) The string is finished (Totally Traversed)

(ii) The stack is empty.

(b) Accepted by final state: A string w may be declared accepted by Final state if after total traversal of the string w the PDA enters into its Final state. In Mathematical notation we can say be a PDA, the string w is declared accepted by Final State if for and z₀ is the stack bottom symbol}.

In general we can say that a string is accepted by a PDA by Final State if both the following conditions are fulfilled

(i) The string is finished (totally traversed)

(ii) The PDA enters into its final state.

(Though there are two way to declare a string accepted by a PDA, but it can be proved that both the ways are equivalent. In general for both the cases all the steps are same, except the last step. In the last step it is differentiated whether the string is accepted by empty stack or by final state.

if in the last step it is accepted by empty stack

if                  it is accepted by final state.)

Q. Prove that a Language is accepted by a PDA by empty stack if and only if the language is accepted by a PDA by final state.

Ans. Let is a PDA. Let it accept a language L by final state. Let there exist another PDA M₂, which accepts the same language L by empty stack.

Let

Where

The transitional function is defined as follows

(a) contains

(b) is the same as for all and

(c) contains and for all

(d) contains for all

(Here (a) describes that M₂ enters in the initial configuration of M₁ with as the leftmost push down symbol.

(b) describes to make M₂ to simulate the behavior of M₁, thus reading an input word w if M₁ reads w and enters a final state. Once w is read and M₂ enter a final state of M₁, the effect of 3 and 4 are to empty the pushdown store.)

Here if and only if

where q_f is the fi nal state of machine M₁.

By rule (a) we can write

i.e. i.e. L is accepted by empty store by M₂.

Conversely, let be a PDA accepting L by empty store

Then

Where

1. contains

2. is the same as for all

3. contains for all

From these two it can be proved that a language is accepted by a PDA by empty stack if and only if the language is accepted by a PDA by final state.

6.3 EXAMPLES

Q. Construct a PDA to accept a given language L by empty stack and final state both where L = (aⁿbⁿ, where n≥1)

Ans. The string is aⁿbⁿ where n≥1. The remarks we can draw from seeing the string aⁿbⁿ where n ≥ 1 are the following.

(a) The string consists of two alphabets 'a' and 'b'.

(b) 'a' will occur before 'b'.

(c) Number of 'a' are equal to number of 'b'.

(d) There will be at least one 'a' and one 'b' in the string.

We have to check equal number of 'a' and 'b'. Let take a stack symbol z₁, which is pushed into the stack as an 'a' is traversed from the input tape. At the beginning, the PDA is in state q₀ and stack top is z₀ as at the beginning there is no other symbol in the stack. In this state it will get an input 'a' from the input tape (the string starts with 'a'). So a stack symbol z₁ will be pushed to the stack. The δ function will be

(At the right-hand-side the stack denotes the placement of the symbols. z₁z₀ denotes that there was z₀ in the stack. Now the symbol z₁ is pushed into the stack. It is given for better understanding of the placement of stack symbols)

From the next input 'a' from the input tape, the PDA is in state q₀ and stack top is z₁, so another z₁ will be pushed into the stack. The δ function will be

By this δ function all the remaining 'a's will be traversed. After the end of 'a' in the input tape, 'b' will occur. When first 'b' will occur on the input tape at that time the PDA is in state q₀ with stack top z₁ (Just before it 'a' s are traversed). When 'b' will traversed the stack top z₁ will be popped and the PDA will change its state to q₁. (So that there will be no chance to push z₁ in the stack if any 'a' occur. The PDA is designed only for string aⁿbⁿ, but the input string may not be in the form of aⁿbⁿ. In that case the string will not be accepted by the PDA.) The δ function will be

When next 'b' will occur, the PDA is in state q₁ with stack top z₁. That z₁ will be popped. The δ function will be

By this δ function all the remaining 'b' will be traversed.

If the input string is in the form of aⁿbⁿ where n ≥ 1 then after traversing the last 'b' the PDA will be in state q₁ with stack top z₀ (All other stack symbols are removed).

If we have to design the PDA accepted by Empty stack the δ function will be

If we have to design the PDA accepted by Final State the δ function will be

So the PDA for L = (aⁿbⁿ, where n ≥ 1) is

δ is defined as follows:

Q. Construct a PDA to accept L = (a,b)^* with equal number of 'a' and 'b', i.e. n_a(L) = n_b(L) by empty stack and final state.

Ans. The string is any combination of 'a' and 'b' including null and number of 'a' is equal to number of 'b'. In the language set a string may start with 'a' or a string may start with 'b'. An 'a' can come after 'a' or 'b' can come after 'a', same like 'a' can come after 'b' or 'b' can come after 'b'. If a string start with 'a' then push a stack symbol z₁ in the stack. If a string start with 'b' then push a stack symbol z₂ in the stack. For these two cases the PDA is in state q₀. The δ function for these two cases will be

If the string starts with 'a' and 'a comes after 'a' then the PDA is in state q₀ with stack top z₁. Another z₁ will be pushed to the stack. The δ function will be

If the string starts with 'a', and 'b' comes after 'a' then the PDA is in state q₀ with stack top z₁. The stack top will be popped from the stack as one 'b' is found after one 'a'. The δ function will be

If the string starts with ' b' and 'b' comes after 'b' then the PDA is in state q₀ with stack top z₂. Another z₂ will be pushed to the stack. The δ function will be

If the string starts with 'b', and 'a' comes after 'b' then the PDA is in state q₀ with stack top z₂. The stack top will be popped from the stack as one 'a' is found after one 'b'. The δ function will be

By these δ functions all the input symbols of the input tape will be traversed. The PDA will be in state q₀ with stack top z₀.

If we have to design the PDA accepted by empty stack the δ function will be

If we have to design the PDA accepted by Final State the δ function will be

(In the Language set null string can occur. If null string occurs in the language set, then it will also be accepted by the last two δ functions directly.)

So the PDA for L = (a,b)^* with equal number of 'a' and 'b', i.e. n_a(L) = n_b(L) is

δ is defined as follows:

Q. Construct a PDA to accept L = (a,b)⁺ with equal number of 'a' and 'b', i.e. n_a(L) = n_b(L) by empty stack and final state.

In the string (a,b)⁺ there will be at least one 'a' and one 'b' with equal number of 'a', and 'b'. So the δ functions of the PDA will be made such that null string will not be accepted. All the conditions are same like (a,b)^* but to avoid null occurrence the transitions will be like this

By getting 'a' at the beginning, change the state from q₀ to q₁ and push z₁ in the stack. From the next input all the transitions will be on state q₁.

Same like, if the string start with 'b', change the state from q₀ to q₁ and push z₂ in the stack. From the next input all the transitions will be on state q₁.

The transitional functions (δ) will be

.(If in the language set there is a null string, there exists no transitional function in the PDA, because the null string will only be traversed if the machine in state q₁. For coming to q₁, it needs to traverse atleast one a ' or one b '. It is clear from the discussion that the PDA will not accept null string, i.e. it is for L = (a,b)⁺ with equal number of 'a' and 'b'.)

Q. Construct a PDA to accept the language L = {WCW^R, where W (a,b)⁺ and W^R is the reverse of W} by empty stack and by final state.

Ans. The W is a string consists of any combination of 'a' and 'b' not including null. The string W may start with 'a' or may start with 'b'. In the string, 'a' may come after 'a' (E.g. aa) or 'b' may come after 'a' (E.g. ab). Or 'a' may come after 'b' [ba] or 'b' may come after 'b' (E.g. bb).

The W^R is the reverse of W. It means if 'a' appears at the ith place from the beginning in W^R, then 'a' must appeared at the ith place from the end in W. The C is the marker which denotes the end of W and beginning of W^R.

The PDA will be designed as follows:

The PDA is in state q₀ with stack top z₀ In the string W if 'a' is traversed as start symbol, a stack symbol z₁ will be pushed and the PDA will change its state to q₁ (To avoid accepting null string). If 'b' is traversed, a stack symbol z₂ will be pushed and the PDA will change its state to q (To avoid accepting null string) .The δ function will be

If in W, 'a' occurs after 'a', then state is q₁ and stack top is z₁. One z₁ will be pushed to the stack. If 'b' occurs after 'a' , then state is q₁ and stack top is z₁. One z₂ will be pushed to the stack. The δ function will be

If in W, 'a' occurs after 'b', then state is q₁ and stack top is z₂. One z₁ will be pushed to the stack. If 'b' occurs after 'b', then state is q₁ and stack top is z₂. One z₂ will be pushed to the stack. The δ function will be

By the already given transitional functions the string W will be traversed.

At the end of W the input head will come to the symbol C to traverse it. The C indicates that the string W is finished and W^R will start. Before traversing C, either 'a' or 'b' is traversed. When C is going to be traversed, at the stack top there will be either z₁ (if just before 'a' is traversed) or z₂ (if just before 'b' is traversed). Upon traversing C only there will be a state change from q₁ to q₂ but no operation will be done on stack. The δ function will be

After traversing C the reverse string of W, i.e. W^R will come. If 'a' comes at the i^th place from the beginning then 'a' will come at the i^th place from the end in W. If for the string W^R as an input 'a' comes, the stack top will be z₁ and state will be q₂. If for the string W^R as an input 'b' comes, the stack top will be z₂ and state will be q₂. This stack top will be popped from the stack. The δ function will be

By these δ functions all the input symbols of the input tape will be traversed. The PDA will be in state q₂ with stack top z₀.

If we have to design the PDA accepted by Empty stack the δ function will be

If we have to design the PDA accepted by Final State the δ function will be

The PDA for L = {WCW^R, where W (a,b)⁺ and W^R is the reverse of W} is

δ is defined as follows:

Q. Construct a PDA to accept the language L = { WCW^R, where W (a, b)^* and W^R is the reverse of W} by Empty stack and by Final state.

Ans. The string W may contain null string. If W is null then W^R is null. It means in the language set there will be only C if W is null. The PDA will always be in state q₀ at the time of traversing the string W. The δ functions for traversing W will be

Here C indicates the end of W and beginning of W^R. When C will be traversed a state change from q₀ to q₁ will occur. The string W may be null. The set L may contain only C. So, stack top will one of the followings at the time of traversing C

May be z₁ (if just before 'a' is traversed)

May be z₂ (if just before 'b' is traversed)

May be z₀ (if no input alphabet is traversed, i.e. W is null).

The δ function for traversing C will be

By the previous given δ functions all the input symbols of the input tape will be traversed. The PDA will be in state q₁ with stack top z₀.

If we have to design the PDA accepted by Empty stack the δ function will be

If we have to design the PDA accepted by Final State the δ function will be

Q. Construct a PDA to accept the language L = {aⁿb^mc^mdⁿ, where m,n ≥ 1} by empty stack and by final state.

Ans. The string is aⁿb^mc^mdⁿ, where m,n ≥ 1. The remarks we can draw from the string are as follows

(a) The string consists of a, b, c and d.

(b) 'b' will follow 'a', 'c' will follow 'b' and 'd' will follow 'c'.

(c) Number of 'a' is equal to number of 'd' and number of 'b' is equal to number of 'c'.

(d) In all the strings of the language set there will be at least one 'a' , one 'b', one 'c' and one 'd'.

We need to check equal number of 'a' and 'd' and equal number of 'b' and 'c'. The string starts with 'a', so in the input tape 'a' will come first with state q₀ and stack top z₀. A stack symbol z₁ will be pushed to the stack. From the next appearance of 'a' in the input tape, stack top will be z₁. Another z₁ will be pushed to the stack. The δ function for traversing 'a' will be

After complete traversal of 'a' in the input tape, 'b' will come to be traversed. At the time of traversal of first 'b' in the input tape, the PDA will be in state q₀ with stack top z₁ (Before it all 'a's are traversed). A state change from q₀ to q₁ will occur and a stack symbol z₂ will be added to the stack. From the next appearance of 'b' in the input tape, the state will be q₁ and stack top will be z₂. Another z₂ will be pushed to the stack. The δ function for traversing 'b' will be

After complete traversal of 'b' in the input tape, 'c' will come to be traversed. The number of 'b' and number of 'c' are equal in all strings belongs to the Language set L. At the time of traversal of first 'c' in the input tape, the PDA will be in state q₁ with stack top z₂ (Before it all 'b's are traversed). A state change from q₁ to q₂ will occur and stack top symbol z₂ will be popped from the stack. From the next appearance of 'b' in the input tape, the state will be q₂ and stack top will be z₂.The symbol z₂ will be popped from the stack. The δ function for traversing 'b' will be

When all the 'c' will be traversed, the stack top will be z₁, which was added at the time of traversal of 'a' and the PDA will be in state q₂. At the time of traversal of first 'd' in the input tape, the PDA will be in state q₂ with stack top z₁. A state change from q₂ to q₃ will occur and stack top symbol z₁ will be popped from the stack. From the next appearance of 'd' in the input tape, the state will be q₃ and stack top will be z₁. The symbol z₁ will be popped from the stack. The δ function for traversing 'b' will be

By the previous given δ functions all the input symbols of the input tape will be traversed. The PDA will be in state q₃ with stack top z₀.

If we have to design the PDA accepted by Empty stack the δ function will be

If we have to design the PDA accepted by Final State the δ function will be

The PDA for L = {aⁿb^mc^mdⁿ, where m,n ≥ 1} is

δ is defined as follows:

Q. Construct a PDA to accept the language L = {aⁿbⁿc^md^m, where m,n ≥ 1} by Empty Stack and by Final State.

Ans. Here number of 'a' and number of 'b' are same and number of 'c' and number of 'd' are same. State change will occur in transition from 'a' to 'b', 'b' to 'c' and 'c' to 'd'. Upon traversing 'a', stack symbol z₁ will be pushed to the stack. Number of 'b' are same as number of 'a'. Number of z₁ pushed to the stack will be equal to number of 'a', i.e. number of 'b'. For traversal of each 'b' in the input tape one z₁ will be popped from the stack.

When first 'c' will be traversed the stack top will be z₀.Upon traversing 'c', stack symbol z₂ will be pushed to the stack. Upon traversing ' d' those z₂'s will be popped from the stack.

By these process all the string will be traversed. The PDA for accepting the string aⁿbⁿc^md^m/m,n ≥ 1 will be

The transition function for constructing PDA for the string aⁿbⁿc^md^m/m,n ≥ 1 will be

Q. Construct a PDA to accept the language L = {aⁿb²ⁿ, where n ≥ 1} by empty stack and by final state.

Ans. In the language set L each string is in the form aⁿb²ⁿ where n ≥ 1. Number of 'b' is double to number of 'a'. At the time of traversing a single 'a' from the input tape two z₁ as stack symbol will be pushed to the stack.

These two z₁ will be popped at the time of traversing two 'b'. [Single 'a' is equal to two 'b'].

The δ function for traversing 'b' will be

By the previous given δ functions all the input symbols of the input tape will be traversed. The PDA will be in state q₁ with stack top z₀.

If we have to design the PDA accepted by Empty stack the δ function will be

If we have to design the PDA accepted by Final State the δ function will be

The PDA will be as follows:

The transitional function will be

Q. Construct a PDA for the language L = {aⁿCb²ⁿ, where n ≥ 1}.

Ans. In the language set number of 'b' is twice of 'a'. The 'C' is the middle element, which indicates the end of 'a' and beginning of 'b'. For each 'a', two z₁ are inserted in the stack, for each 'b', one z₁ is popped from the stack.

The transitional functions are

Q. Construct a PDA for the language L = {a^mbⁿ where m ≤ n and m,n ≥ 1}

Ans. In the language set number of 'a' is less than number of 'b'. At the time of traversing 'a', one z₁ is added to the stack. For m number of 'a', m number of z₁ are added to the stack. At the time of traversing m number of 'b', stack top is z₁, which is popped. If n > m, then at the time of traversing last (n–m) number of 'b', stack top is z₀.

The transitional functions are

Q. Construct a PDA to accept the language L = {aⁿb^mc^n+m, where n > 0, m > 0}

Ans. In the language set total number of 'c' is equal total number of 'a' and 'b'. The PDA can be designed in the following way, at the time of traversing n number of 'a', n number of 'z₁' are added to the stack and for traversing m number of 'b', m number of z₁ are added to the stack. At the time of traversing (n + m) number of c all the z₁ are popped from the stack.

The transitional functions are:

Q. Construct a PDA to accept the language L = {aⁿb^mcⁿ + ^m, where n ≥ 0, m > 0}

Ans. The string is same as the previous but in the language set number of 'a' may be zero. In the case when number of 'a' is zero, then the string starts from 'b'.

The transitional functions are

Q. Construct a PDA to accept the language L = {aⁿb^n+mc^m, where n,m > 0}

Ans. In the language set number of 'b' is total number of 'a' and 'c'. At the time of traversal of n number of 'a', n number of z₁ are pushed in the stack, at the time of traversal of n number of 'b', n number of z₁ are popped from the stack. At the time of traversal of rest m number of 'b', m number of z₂ are pushed into the stack, which are popped at the time of traversal of m number of 'c'.

The transitional functions are

Q. Construct a PDA to accept the language L = {aⁿb^n+mc^m, where n ≥ 0 m > 0 }

Ans. The string is same as the previous but in the language set number of ' a may be zero. In the case when number of 'a is zero, then the string starts from 'b'.

The transitional functions are

Q. Construct a PDA to accept the following language L = {a²ⁿbⁿ, where n > 0 }

Ans. In the language set number of 2n number of 'a' and n number of 'b'. The PDA can be designed as follows – at the time of traversing first 'a', two z₁ are added to the stack with a state changed from q₀ to q₁. At the time of traversing second 'a' one z₁ is popped from the stack with a state change from q₁ to q₀. By this process after traversing 2n number of 'a only n number of z₁ exist in the stack. At the time of traversing first 'b' stack top is z₁ and state q₀. Those z₁ are popped at the time of traversing n number of 'b'.

The transitional functions are

Q. Construct a PDA to accept the language L = {aⁿbⁿc^m, where n,m ≥ 1} by empty stack and by final state.

Ans. The language is in the form aⁿbⁿc^m, where n,m ≥ 1. In the language set number of 'a' and number of 'b' are same, but number of 'c' is different. All the strings in the language set starts with n number of 'a's followed by n number of 'b's and ends with m number of 'c's. Here m and n both ≥ 1, null string does not belongs to the language set.

The PDA for the language can be designed in the following way.

When traversing 'a's from the input tape, one by one z₁ are pushed in the stack. At the time of traversing 'b's, all the z₁'s which were pushed into the stack are popped one by one. When first 'c' will be traversed, at that time the machine is in state q₁ and stack top z₀. At the time of traversal of m number of 'c's, no operation is done on stack.

The transition function for constructing PDA for the string aⁿbⁿc^m where m,n ≥ 1 are

Q. Construct a PDA to accept the language L = {aⁿb^mcⁿ, where n,m ≥ 1} by empty stack and by final state.

Ans: The language is in the form aⁿb^mcⁿ, where n,m ≥ 1 . In the language set, number of 'a's are equal to number of 'c's. In the language set, 'a's are separate with 'c's by m number of 'b's. As m,n ≥ 1, null string does not belong to the language set. In the language set number of 'a' are equal to number of 'c' but not with number of 'b'.

The PDA can be designed in the following way:

When traversing 'a's from the input tape, one by one z₁ are pushed in the stack. When the first 'b' is read by the input head, the machine is in state q₀ and stack top z₁. One state change has occurred. (If after 'b' again 'a' comes as input, the language is in wrong format. But that 'a' will also be traversed as there will be a function

to traverse that 'a'. To avoid this mismatch and to guarantee that the PDA is only for accepting a^n-' b^mcⁿ, where n,m ≥ 1, the state change is required.) At the time of traversing 'b', no operation is done on the stack.

When 'c' will going to be traversed, the machine is in state q₁, with stack top z₁. The stack top is popped and a state change has occurred. (To avoid appearance of 'b' after 'c').

The transition function for constructing PDA for the string aⁿbⁿc^m where m,n ≥ 1 will be

Q. Construct a PDA to accept the language L = {w, where number of 'a' + number of 'b' = number of 'c'}

Ans. According to the given specification any string belong to the language set consists of any combination of 'a', 'b' and 'c' and number of 'c' is equal to number of 'a' and number of 'b'. In the string 'a', 'b' and 'c' can occur in any sequence with fulfilling the given condition.

The transitional functions are

6.4 DETERMINISTIC PDA AND NON-DETERMINISTIC PDA

Q. How many types of PDA are there? Describe each of them by suitable example.

Ans: There are two types of PDA:

(a) Deterministic PDA (DPDA)

(b) Non-Deterministic PDA (NPDA)

(a) Deterministic PDA (DPDA): A PDA is said to be a DPDA if all derivations in the design give only single move.

If a PDA being in a state with a single input and single stack symbol gives a single move, then the PDA is called Deterministic PDA.

As an example for L = {aⁿbⁿ, where n ≥ 1} can be designed a DPDA if the transitional functions are as following.

In the previous PDA, in a single state with a single input and single stack symbol there is only one move. So the PDA is deterministic.

(b) Non-Deterministic PDA (NPDA): A PDA is called non-deterministic if one of the derivations generates more than one move.

If a PDA being in a state with a single input and single stack symbol gives more than one move for any of its transitional functions, then the PDA is called Non-Deterministic PDA.

Q. Design a non-deterministic PDA for accepting the string {WW^R where W (a,b)⁺ and W^R is the reverse of W} by empty stack and by final state.

Ans. The W is a string consists of 'a' and 'b'. The W^R is the reverse string of W Let W = abaa, then W^R will be aaba. WW^R will be abaaaaba. Traversing input symbol 'a' from the input tape, z₁ will be pushed into the stack and traversing input symbol ' b' from the input tape, z₂ will be pushed into the stack. When W^R will start, for the traversal of first symbol the state of the PDA will be changed and the stack top will be popped. From the next input symbols belong to W^R the stack top will be popped.

But here is a problem. In the PDA it is not assigned where W is ended and W^R is started. The PDA will traverse the total string assuming it as W. Some attempt has been done to differentiate W and W^R by traversing a λ symbol and changing the state in between Wand W^R. But this is also wrong, as all the input symbols are placed on the input tape from left to right in a continuous fashion. There is no gap in between two input symbols, as they are placed one by one in each square from left to right on the input tape.

From the above discussion it is clear that a Deterministic PDA cannot be designed for WW^R.

But this is possible for Non-deterministic PDA. Our problem is to find the middle of the string where W ends and W^R starts. In the string where consecutive two 'a' and two 'b' appear, that may be the middle of the string, because the last alphabet of Wis the first alphabet of W^R. Make two transitional functions when stack top is z₁ and 'a' is traversed as input and stack top is z₂ and ' b' is traversed as input. (All the other δ functions are same as WCW^R). The PDA for accepting the string WW^RI We (a,b)+ and W^R is the reverse of W is

The transitional function will be

Q. Design a non-deterministic PDA for accepting the string { WW^R where W (a,b)^* and W^R is the reverse of W} by empty stack and by final state.

Ans. Null string may belong to the Language set. The PDA will be designed in such a way that null string can be accepted by the PDA. The transitional functions will be:

Q. Design a Non-Deterministic PDA for accepting the string L = {(Set of all palindromes over a, b)} by empty stack and by final state.

Ans. A string read from left to right and right to left gives the same result is called palindrome. Palindrome can be of two types (a) Odd Palindrome (b) Even Palindrome. Odd palindromes are those where number of characters is odd and even palindromes are those where number of characters is even.

The string 'a' is a palindrome, 'b' is a palindrome. 'aa' is a palindrome, 'bb' is a palindrome. The string 'aba' is a palindrome, 'aaa', 'bbb' are also palindrome. Null string is also a palindrome.

The PDA will be

Transitional functions are as follows

6.5 PUSHDOWN AUTOMATA FROM CONTEXT FREE GRAMMAR

Q. How to construct an equivalent PDA of a context free grammar.

Ans.

Step I: Convert the PDA into Greibach Normal Form (GNF).

Step II: First the start symbol S of the CFG is put to the stack by transition function

Step III: For a production in the form {NT₁} {Single T}{String of NT}, the transitional function will be

Step IV: For a production in the form {NT₁} {Single T}, the transitional function will be δ(q₁, T, NT₁) (q₁, λ).

Step V: For accepting a string two transitional functions are added, one for accepted by empty stack and one for accepted by final state.

Q. Construct a PDA that accept the language generated by the following grammar

Show an ID for the string abab for the PDA generated.

Ans.

The Context Free Grammar is in GNF.

First the start symbol S is pushed into the stack by the following production

For the production S aB the transitional function is

For the production A aB the transitional function is

For the production B bA/b the transitional function is

So, the PDA for the above CFG is

δ functions are defined as follows:

Id for the string abab.

(The process is very easy. First try to generate the string from the given grammar by left most derivation. Then according to the non terminal symbols replaced use the particular transitional function to give the ID

For the previous case the string ‘abab’ is generated like the derivation(Left Most) given below S

First transitional function is adding S in the stack. After that S is replaced by B for the input ‘a’ using the transitional function δ (q₁, a, S) (q₁, B)

The process continues like this till the end of the string.)

Q. Construct an equivalent PDA for the following Context Free Grammar.

Show an ID for the string abbaaabbbbab for the PDA generated with stack description.

Ans. The CFG is in GNF.

First the start symbol S is pushed into the stack by the following production

For the production S aAB, the transitional function is

For the production S bBA, the transitional function is

For the production A bS, the transitional function is

For the production B aS, the transitional function is

For the production A a, the transitional function is

For the production B b, the transitional function is

For acceptance transitional function is

Id for the string abbaaabbbbab

Q. Construct an equivalent PDA for the following CFG.
S 0BB
B 0S/1S/0

Show an ID for the string 010000 for the PDA generated.

Ans. First the start symbol S is pushed into the stack by the following production

For the production S 0BB, the transitional function is

For the production B 0S, the transitional function is

For the production B 1S, the transitional function is

For the production B 0, the transitional function is

For acceptance transitional function is

Id for the string 010000

Q. Construct an equivalent PDA for the following CFG.

S aA

A aABC/bB/a

C c

Show an ID for the string aabbbc for the PDA generated.

Ans.

First the start symbol S is pushed into the stack by the following production

For the production S aA, the transitional function is

For the production A aABC, the transitional function is

For the production A bB, the transitional function is

For the production A a, the transitional function is

For the production C c, the transitional function is

For acceptance transitional function is

Id for the string aabbbc

Q. Construct an equivalent PDA for the following CFG.

S aSbb/aab

Show an ID for the string aaabbb for the PDA generated.

Ans. The given grammar is not in GNF. First we need to convert the grammar into GNF. Replace ‘b’ by Band ‘a’ by A. The converted grammar in GNF is

S aSBB/aAB

A a

B b

Now the grammar can be easily converted into PDA.

The transitional functions for the PDA accepted by the language generated by the grammar are

ID for the string aaabbb

6.6 GRAPHICAL NOTATION FOR PDA

Q. How a PDA can be denoted by graphical notation?

Ans. The mathematical notation for a PDA is In a PDA the transitional function δ consists of three touples, first is a present state, second is present input and the third is stack top symbol; which generates one next state and stack symbol(s) if a symbol is pushed into the stack or ε, if the top most symbol is popped from the stack.

In the graphical notation of PDA there are states. Among them a circle with an arrow indicates a beginning state and a state with double circle indicates a final state. The state transitions are denoted by arrow. The labels of the state transitions consists of input symbol, stack top symbol and the stack top symbol which is added after the transitions or null is a symbol is popped.

Q. Construct a PDA with graphical notation to accept L = (a, b)^* with equal number of ‘a’ and ‘b’, i.e. n_a(L) = n_b(L) by final state.

Ans. At the beginning of transition the PDA is in state q₀ with stack to z₀. The string may start with 'a’ or ‘b'. If the string start with ‘a', one z₁ is pushed into the stack. If the string start with ‘b’, one z₂ is pushed into the stack. If ‘b’ is traversed after ‘a’, and stack top is z₁, and that stack top is popped. If ‘a’ is traversed after ‘b’, and stack top is z₂, and that stack top is popped. If ‘a’ is traversed after ‘a’, and stack top is z₁, and one ‘z₁’ is pushed into the stack. If ‘b’ is traversed after ‘b’, and stack top is z₂, and one ‘z₂’ is pushed into the stack.

The PDA in graphical notation is

Q. Construct a PDA with graphical notation to accept the language L = {WCW^R, where W ∈ (a,b)⁺ and W^R is the reverse of W} by Final state.

Ans. At the beginning of the transition the machine is in state q₀ and stack top symbol z₀. If it gets input symbol ‘a’, one z₁ is pushed into the stack, if it gets input symbol ‘b’, one z₂ is pushed into the stack and state is changed from q₀ to q₁. In state q₁ if it gets input ‘a’ and stack top z₁ or z₂ another z₁ or z₂ is pushed into the stack, respectively. In state q₁ if it gets input 'b’ with stack top z₂ or z₁, another z₂ or z₁ is pushed into the stack, respectively.

The C is the symbol which differentiate W with W^R. Before C, W is traversed. Therefore, at the time of traversing C, stack top symbol may be z₁ or z₂. In state q₁ if the PDA gets C as input and stack top z₁ or z₂, no operation is done on the stack, only state is changed from q₁ to q₂. After C the string W^R is traversed. If the machine gets ‘a’ as input, stack top must be z₁. And that z₁ is popped from the stack top. If the machine gets ‘ b’ as input, stack top must be z₂. And that z₂ is popped from the stack top. The state is not changed. By this process the whole string WCW^R is traversed. In state q₂ if the machine gets no input but stack top z_o, the machine goes to its final state q_f.

The graphical notation for the PDA is

WHAT WE HAVE LEARNED SO FAR

1. PDA (in short PDA) is the machine format of CFL.

2. The mechanical diagram of a PDA contains Input tape, Reading head, Finite control and a stack.

3. A PDA consists of 7-touple M = (Q, ∑, Γ, δ, q_o, z_o, F), where Q, ∑, q_o and F has their original meaning, Γ is finite set of stack symbols and z_o is the stack bottom symbol.

4. In PDA transitional function δ is in the form

5. Instantaneous Description (ID) remembers the information of state and stack content at a given instance of time.

6. There are two ways to declare a string accepted by a PDA (a) accepted by empty stack (store) (b) accepted by final state.

7. A string is declared accepted by a PDA by empty stack if the string is totally traversed and the stack is empty.

8. A string is declared accepted by a PDA by Final state if the string is totally traversed and the machine reaches to its final state.

9. A string accepted by a PDA by empty stack if and only if the language is accepted by that PDA by final state.

10. If a PDA being in a state with a single input and single stack symbol gives a single move, then the PDA is called Deterministic PDA.

11. If a PDA being in a state with a single input and single stack symbol gives more than one move for any of its transitional functions, then the PDA is called Non Deterministic PDA.

12. From Context free grammar NPDA can be directly constructed.

SOLVED PROBLEMS

1. Design a PDA to accept the language of nested balanced parentheses.[Where number of opening and close parenthesis is greater than 0]

Ans. Nested balanced parenthesis is in the form ((())). More precisely

   (
    (
     (
     )
    )
   )

This type of nested balanced parentheses has two types of symbol open parenthesis ‘(’ and close parenthesis ‘)’. As it is nested, first the PDA has to traverse open parenthesis after that the close parenthesis.

The transitional function for traversing the first open parenthesis is (The beginning state is q₀, input symbol is ‘(’ and stack top is z₀. )

From then on the state is q₀, input symbol is ‘(’ [if number of open parenthesis is > 1] and stack top is z₀. The transitional function for traversing the next open parenthesis is

By using the previous transitional function all the remaining open parenthesis will be traversed.

After traversing all open parentheses the PDA will get the first close parenthesis. At that time the state is q₀, input symbol is ‘)’, and stack top is z₁. After getting the ‘)’ as an input symbol the stack top [here z₁] will be popped from the stack and state will be changed to q₁. The transitional function is

After that the state is q₁, input symbol is ‘)’ and stack top is z₁. (If the string contain multiple open and close parentheses). The transitional function is

When all input symbols are traversed the PDA is in state q₁, input symbol is λ and stack top is z₀.

If we have to design the PDA accepted by empty stack the δ function will be

If we have to design the PDA accepted by final State the δ function will be

The transitional functions for the PDA is

2. Design a PDA to accept the language of balanced parentheses. (Where number of opening and close parenthesis is greater than 0.)

Ans. There are two types of parentheses - open parentheses and close parentheses. Balanced parenthesis means for each open parenthesis there is a close parenthesis. It may be nested like ( ( ( ) ) ) or may be non nested like ( ( ) ( ) ) or ( )( )( ) or any other form. But for each open parenthesis there is a close parenthesis. (The definition that balanced parenthesis means equal number of open and close parentheses is wrong. As an example, ) ( )( ) ( is not a balanced parenthesis). The string must start with an open parenthesis and after that open parenthesis or close parenthesis can appear, but for any position of the string, number of open parenthesis is greater than or equal to number of close parenthesis.

The transitional function for traversing the first open parenthesis is (The beginning state is q₀, input symbol is ‘(’ and stack top is z₀.)

(As null string is not accepted by the PDA).

After the first open parenthesis, there may be open parenthesis or close parenthesis. If open parenthesis is to be traversed then a z₁ is added at the stack top. The transitional function is

If close parenthesis is to be traversed then one z₁ is popped from the stack top. The transitional function is

It may happen that the state is q₁, and stack top is z₀ and the input symbol is ‘(’. [As an example for the case (())()] The transitional function for the case is

(But this type of case can not appear -where the state is q₁, and stack top is z₀ and the input symbol is’)’)

If we have to design the PDA accepted by empty stack the δ function is

If we have to design the PDA accepted by final state the δ function is

The transitional functions for the entire PDA is

3. Design a PDA to accept the language L = a^mbⁿc^m-n, where m > = n and m, n > 0

Ans. The language consists of 'a’, ‘b’ and ‘c’. Here in every string all ‘a’ will appear before ‘b’ and after ‘b’, ‘c will appear. Number of ‘c is the subtraction of number of ‘a’ and number of ‘b’. At the beginning the machine is in state q_o with stack top z_o and input is ‘a’. After traversing, the machine will add z₁ in the stack. The transitional function is

If number of ‘a’ is greater than one then the machine have to traverse ‘a’ with state q_o and stack top z₁. Another z₁ is added to the stack top. The transitional function is

After traversal of all ‘a', ‘b’ will appear. When ‘b’ will come at that time state is q_o, stack top is z₁ .The stack top is popped from the top. The transitional function is.

If number of ‘ b’ is greater than one then the machine has to traverse ‘b’ with state q₁ and stack top z₁. (Number of ‘b’ greater than one means number of ‘a’ was greater than one.) The stack top is popped from the top. The transitional function is.

If number of ‘b’ is less than number of ‘a’, then ‘c’ will appear after fully traversal of all ‘b's. At that time the state is q₁, and stack top is z₁. After traversal of ‘c’, the stack top is popped. The transitional function is.

If number of ‘c’ is greater than one then the machine have to traverse ‘c’ with state q₂ and stack top z₁. (Number of ‘c’ greater than one means number of ‘a’ was greater than one.) The stack top is popped. The transitional function is.

If we have to design the PDA accepted by empty stack the δ function is

If we have to design the PDA accepted by Final State the δ function is

It may also happen that m = n, i.e. number of ‘a’ is equal to number of ‘b’. At that case there is no ‘c’ in the language. The string ends after fully traversal of all ‘b’. After traversal of all ‘b’ s the state of the machine is q₁. If we have to design the PDA accepted by empty stack the δ function is

If we have to design the PDA accepted by final state the δ function is

The transitional functions for the entire PDA is

4. Design a PDA to accept the language L = aⁿb^mc^m-n where m > n and m, n > 0.

Show an ID for the string aabbbbcc.

Ans. The language consists of ‘a', 'b' and ‘c . Here in every string all ‘a’ will appear before ‘b’ and after ‘b’, ‘c’ will appear. Number of ‘c’ is the subtraction of number of ‘b’ and number of ‘a’. In the string number of 'b’ is the sum of number of ‘a’ and number of ‘c’. It can be designed as follows: For n number of 'a’ , n number of z₁ are added to the stack. For next n number of b, those z₁ are popped from the stack and z₀ becomes the stack top. For the remaining (m-n) number of ‘b', (m-n) number of z₂ are added to the stack. For (m-n) number of 'c’, (m-n) number of z₂ are popped from the stack.

The transitional functions are designed as follows.

At the beginning the machine is in state q₀ with stack top z₀ and input is ‘a'. After traversing, the machine will add z₁ in the stack. The transitional function is

If number of 'a’ is greater than one then the machine have to traverse 'a’ with state q₀ and stack top z₁ Another z₁ is added to the stack top. The transitional function is

After traversal of all 'a’, ‘b' will appear. When 'b' will come at that time state is q₀, stack top is z_r The stack top is popped from the top. The transitional function is.

If number of 'a’ is greater than one then number of 'b' is also greater than one because m = (m-n) + n. The machine has to traverse 'b' with state q_l and stack top z₁ The stack top is popped from the top. The transitional function is.

After some time all z₁ s are popped from the stack. The stack top becomes z₀. As m is greater than n, till the input symbol is 'b' with machine state q₁. In this situation z₂ is pushed into the stack. The transitional function is

If m-n is greater that one, i.e. number of ‘c’ is more than one then machine state q₁, input symbol 'b' and stack top z₂. Another z₂ is pushed into the stack. The transitional function is

After fully traversal of all ‘ b's,'c’ appears in the string. When ‘c' appears machine state is q₁ and stack top is z₂. The stack top z₂ is popped from the stack. The transitional function is.

If m-n is greater that one, i.e. number of ‘c’ is more than one the machine has to traverse ‘c’ with state q₂ and stack top z₂. The stack top z₂ is popped from the stack. The transitional function is

If we have to design the PDA accepted by empty stack the δ function is

If we have to design the PDA accepted by final State the δ function is

The transitional functions for the entire PDA is

ID for the string aabbbc

5. Design a PDA for Hypertext Markup Language (HTML) consisting of all tags having immediate closing tags within the <BODY></BODY> tag.

Show an ID for the following language

 <HTML>
   <HEAD>
    <TITLE>
    My First Web Page
    </TITLE>
   </HEAD>

 <BODY>
  <B>First Web Page</B>
  <p><B>HTML</B> is an <I>interpreted language.</I> No error is produced in HTML.
  </p>
  </BODY>
</HTML>

Ans. Hypertext Markup Language (HTML) is a language used for webpage designing. This language is an interpreted language and produces no error. The language has a basic structure in the following form

<HTML>
  <HEAD>
   <TITLE>
   ----------
   </TITLE>
  </HEAD>
  <BODY>
  Some other tags with closing tags 
  </BODY>
<HTML>

The tags can be of capital letter, small letter or mixture of both. The tags within <> is called open tag and the tags within </> is called closing tags. Most of the tags in HTML has closing tags, but some of the tags like <BR>, <HR> has no closing tags.

In <BODY> </BODY> tag all the other tags appear. The tags may appear in any order. But for all the opening tags there is a closing tag except the tags which do not have any closing tag. For the line <B>HTML</B> is an <I>interpreted language.</I>, the output is

HTML is an interpreted language.

If the line is in the form <B>HTML is an <I>interpreted</B> language.</I>, the output:

HTML is an mterpreted language.

In this section we are interested in tags with immediate closing tags like the first example, i.e., the tag within the body which has opened first will close at last.

Every HTML file starts with <HTML> tag. At state q₀, when the machine gets <HTML> as input it pushes Z<_HTML> in the stack. The transitional function is

In every HTML document after <HTML>, <HEAD> tag comes. The transitional function for traversing <HEAD> is

In every HTML document after <HEAD>, <TITLE> tag comes. The transitional function for traversing <TITLE> is

When the machine gets closing </TITLE> tag it pops the stack top symbol Z_<TITLE>. The transitional function

When the machine gets closing </HEAD> tag it pops the stack top symbol Z_<HEAD> The transitional function is

Now the stack top is Z_<HTML> The next symbol is <BODY>. The transitional function for traversing <BODY> tag is

Within <BODY> tag any tag can come. Let a tag named <tag j> has come. Let the state of the PDA is q_i, where i is greater than or equal to 4. For traversing that tag the transition function is

If <tag j> appears with immediate closing tags then its closing tag will get the symbol Z_{<tag j>} as stack top. That stack top is popped.

The last two tags are </BODY> and </HTML>. When </BODY> is traversed the stack top is Z_<BODY>. The stack top is popped by the following transitional function.

When </HTML> is traversed the stack top is Z_<HTML>. The stack top is popped by the following transitional function.

If we have to design the PDA accepted by empty stack the δ function is

If we have to design the PDA accepted by final state the δ function is

ID for the given HTML document:

It is not possible to show the string in each phase. Only the state and the stack condition is shown in the description.

6. Design a PDA for the language L = {aⁿb^ma^mbⁿ, where m, n ≥ 1}

Ans. The language is a CFL. The CFG for the language is S aSb/ aAb

A bAa/ ba

The grammar is not in GNF. So, first we need to convert the grammar into GNF. Take two nonterminals C_a and C_b and two productions C_a a and C_b b. Replacing in appropriate positions the modified context free grammar is

S aSC_b

S aAC_b

A bAC_a

A bC_a

C_a a

C_b b

The CFG is in GNF.

First the start symbol S is pushed into the stack by the following production

For the production S aSC_b the transitional function is

For the production S aAC_b the transitional function is

For the production A bAC_a the transitional function is

For the production A bC_a the transitional function is

For the production C_a a the transitional function is

For the production C_b b the transitional function is

If we have to design the PDA accepted by empty stack the δ function is

If we have to design the PDA accepted by final state the δ function is

7. Construct PDA for the language

Ans. The given language is the union of two languages (ab)ⁿ and (ba)ⁿ. The grammar for the first language is S₁ abS₁/ab. Grammar for the second language is S₂ baS₁/ba. Here we have considered two start symbols S₁ and S₂, respectively. As two languages are connected with union symbol, consider another start symbol for the entire language as S. Make a production rule S S₁/S₂. The production rule for the grammar satisfying the language is

The production rule after removing unit productions and useless symbol is

The grammar is not in GNF. Consider two non-terminals C_a and C_b and two productions C_a a and C_b b. The modified production rule become

The CFG is in GNF.

First the start symbol S is pushed into the stack by the following production

For the production S aC_b the transitional function is

For the production S bC_a the transitional function is

For the production S aC_bS₁ the transitional function is

For the production S bC_aS₂ the transitional function is

For the production S₁ aC_b the transitional function is

For the production S₁ aC_bS_l the transitional function is

For the production S₂ bC_a the transitional function is

For the production S₂ bC_aS₂ the transitional function is

For the production C_a a the transitional function is

For the production C_b b the transitional function is

If we have to design the PDA accepted by Empty stack the δ function is

If we have to design the PDA accepted by final state the δ function is

8. Construct PDA for the language

Ans. The given language is the union of two languages aⁿbⁿ and a^mb^2m. The grammar for the first language is A aAb and A ab.

Grammar for the second language is B aBbb and B abb. Here we have considered two start symbols A and B, respectively. As two languages are connected with union symbol, consider another start symbol for the entire language as S. Make a production rule S A/B. The production rule for the grammar satisfying the language is

S A/B
A aAb/ab
B aBbb/abb

The grammar contains two unit productions S A and S B. After removing the unit productions the production rules become

S aAb/aBbb/abb/ab
A aAb/ab
B aBbb/abb

The CFG is not in GNF. Consider two non-terminals S_a and S_b and two extra production rules S_a a and S_b b. Replacing a and b by S_a and S_b, respectively in suitable places, the modified production rules become.

The CFG is in GNF.

First the start symbol S is pushed into the stack by the following production

For the production S aAS_b the transitional function is

For the production S aBS_bS_b the transitional function is

For the production S aS_bS_b the transitional function is

For the production S aS_b the transitional function is

For the production A aAS_b the transitional function is

For the production A aS_b the transitional function is

For the production B aBS_bS_b the transitional function is

For the production B aS_bS_b the transitional function is

If we have to design the PDA accepted by empty stack the δ function is

If we have to design the PDA accepted by final state the δ function is

MULTIPLE CHOICE QUESTIONS

1. PDA is the machine format of

(a) Type o language    (b) Type 1 language    (c) Type 2 language    (d) Type 3 language.

2. Which is not true for mechanical diagram of PDA?

(a) PDA contains a stack

(b) The head reads as well as writes

(c) The head moves from left to right

(d) Input string is surrounded by infinite number of blank in both side.

3. The difference between finite automata and PDA is in .

(a) Reading Head    (b) Input tape    (c) Finite Control    (d) Stack

4. In PDA transitional function δ is in the form

(a)     (b) Q X Σ Q     (c)     (d) (Where Q is the finite set of states, ∑ is the set of input alphabets, ┌ is the stack symbols.)

5. Instantaneous Description remembers

(a) the information of state and input tape content at a given instance of time.

(b) the information of state and stack content at a given instance of time.

(c) the information of input tape and stack content at a given instance of time.

(d) the information of state, input tape and stack content at a given instance of time

6. Which of the following is not possible algorithmically?

(a) RE to CFG     (b) NFA to DFA    (c) CFG to PDA    (d) NPDA to DPDA

7. Which of the following is not accepted by DPDA but accepted by NPDA?

(a) L = aⁿbⁿ, where n > 0    (b) L = WCW^R, where W ∈ (a, b)^*    

(c) L = WW^R, where W ∈ (a, b)⁺    (d) L = aⁿb^mc^mdⁿ, where m,n > 0

8. Which of the followings cannot be designed by PDA?

(a) aⁿbⁿcⁱ, where n, i > 0 (b) aⁿbⁿcⁿ, where n > 0,

(c) aⁿcⁱbⁿ, where n, i > 0 (d) cⁱaⁿbⁿ, where n, i > 0.

Ans. 1. c,   2.b,    3.d,   4. a,   5. b,   6. d,   7. c,   8. b.

EXERCISES

1. Construct PDA to accept the following languages by empty store and final state.

(a) L = {aⁿ, where n > 0}

(b) L = {aⁿ, where n ≥ 0}

(c) L = {aⁿbcⁿ, where n > 0}

(d) L = {aⁿb²ⁿ, where n > 0}

(e) L = {aⁿb^mc^{m + n}, where m, n > 0}

(f) L = {aⁿbaⁿ, where n > 0}

(g) L = {aⁿbⁿcⁱ, where n, i > 0}

(h) L = {a^mb^m+n cⁿ, where m, n > 0}.

(Hints: For m number of ‘a’, m number of Z₁ are pushed into the stack. For first m number of 'b', m number of Z_l are popped from the stack. For next n number of ‘b’, n number of Z₂ are pushed into the stack, which will be popped for next n number of ‘c'.)

(i) L = {a^mb^m+naⁿ, where m, n > 0}

(j) L = {WCW, where W ∈ (a, b)+}

(k) L = {WCW, where W ∈ (a, b)*}.

2. Construct an equivalent PDA for the following Context Free Grammars.

(a) S aB/bA
A aS/bAA/a
B bS/aBB/b

(b) S bA/aB
A bA/aS/a
B aB/bS/b

(c) S Abb/a
A aaA/B
B bAb

3. Construct PDA with graphical notation to accept the following languages by graphical notation

(a) L = {aⁿbⁿc^md^m, where m,n ≥ 1}

(b) L = {aⁿbⁿc^m, where n,m ≥ 1}.

FILL IN THE BLANKS

1. Full form of PDA is__________.

2. __________ is the machine format of Context Free Language.

3. The mechanical diagram of Pushdown Automata is similar to Finite Automata but difference is in __________.

4. __________ of PDA describes the configuration of PDA at a given instant.

5. There are two ways to declare a string accepted by a Pushdown Automata a)__________ and b) __________.

6. For directly constructing PDA from a given grammar we first need to convert the grammar into __________ normal form.

7. If a PDA being in a state with a single input and single stack symbol gives a single move, then the PDA is called __________ -Pushdown automata.

8. If a PDA being in a state with a single input and single stack symbol gives more than one move for any of its transitional functions, then the PDA is called __________ Pushdown automata.

9. The PDA for the string L = {(Set of all palindromes over a, b)} can be designed by __________ Pushdown automata not by __________ Pushdown automata.

ANSWERS

1. Pushdown Automata

2. Pushdown Automata

3. stack

4. Instantaneous Description (ID)

5. Accepted By Empty Stack,

6. Greibach

7. Deterministic

8. Accepted by Final State Non Deterministic

9. Non Deterministic Deterministic