Define a Push Down Automata. Construct a PDA that accepts L = {an bn | n 0}

Question

Define a Push Down Automata. Construct a PDA that accepts L = {an bn | n > 0}

Bipin Tiwari · Accepted Answer

Pushdown Automata is a finite automata with extra memory called stack which helps Pushdown automata to recognize Context Free Languages. A Pushdown Automata (PDA) can be defined as : Q is the set of states ∑is the set of input symbols Γ is the set of pushdown symbols (which can be pushed and popped from stack) q0 is the initial state Z is the initial pushdown symbol (which is initially present in stack) F is the set of final states δ is a transition function which maps Q x {Σ ∪ ∈} x Γ into Q x Γ*. In a given state, PDA will read input symbol and stack symbol (top of the stack) and move to a new state and change the symbol of stack. Solution This language accepts L = {ε, 01, 0011, 000111, ............................. } Here, in this example, the number of ‘a’ and ‘b’ have to be same. Initially we put a special symbol ‘$’ into the empty stack. Then at state q2, if we encounter input 0 and top is Null, we push 0 into stack. This may iterate. And if we encounter input 1 and top is 0, we pop this 0. Then at state q3, if we encounter input 1 and top is 0, we pop this 0. This may also iterate. And if we encounter input 1 and top is 0, we pop the top element. If the special symbol ‘$’ is encountered at top of the stack, it is popped out and it finally goes to the accepting state q4.

Define a Push Down Automata. Construct a PDA that accepts L = {aⁿbⁿ | n > 0}

Leave your Answer:

Hits Counter

Question

Define a Push Down Automata. Construct a PDA that accepts L = {anbn | n > 0}

Leave your Answer:

Define a Push Down Automata. Construct a PDA that accepts L = {aⁿbⁿ | n > 0}