The string is accepted by the PDA when we get to the acceptance state and see that the stack is empty. Usually, PDAs can accept by accepting state, accepting empty stack, or accepting both empty state and empty stack. Since the last one leaves the least to the imagination, we favour it. In terms of processing capacity, however, they are all exactly comparable definitions.
In this article, we will look more into the PDA Acceptance according to the GATE Syllabus for (Computer Science Engineering) CSE. We will read ahead to find out more about it.
Table of Contents
What is PDA Acceptance?
The term “PDA acceptability” might be defined in two different ways.
Final State Acceptability
When a PDA accepts a string, it must have reached its final state after reading the full string. We can make changes from the initial state that lead to a final state with a stack value. As long as we arrive at a final state, the stack values don’t matter.
Empty Stack Acceptability
Here, a PDA accepts the string when it has cleared its stack after reading the complete string.
Example 1
Let us construct a PDA accepting L = {0n 1n | n ≥ 0}
Solution
The language accepts L = {ε, 01, 0011, 000111, ……………………….. }
Thus, in this example, the total number of ‘a’ and ‘b’ must be the same.
- In the beginning, we added the special symbol “$” to the empty stack.
- If input 0 is encountered at state q2 and the top is Null, then we push 0 into the stack. This might repeat. And we pop this 0 if input 1 is encountered and the top is 0.
- Then, if input 1 is encountered at state q3 and the top is 0, then we pop this 0. This could potentially be repeated. Additionally, if input 1 is encountered and the top is 0, the top element is popped.
- The special symbol “$” is popped out if it appears at the top of the stack and then moves to the accepting state q4.
Example 2
Let us construct a PDA accepting L = { wwR | w = (a+b)* }
Solution
In the beginning, we added the special symbol “$” to the empty stack. It is reading the w at state q2. Each 0 or 1 in state q3 is popped whenever it matches the input. Any more input will cause the PDA to enter a dead state. Move to the q4 accepting state when we encounter the unique sign “$.”
Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility Criteria, GATE 2023, GATE Admit Card, GATE Syllabus, GATE Previous Year Question Paper, and more.
