Home Â» Automata PDA Acceptance

PDA Acceptance

A language can be accepted by Pushdown automata using two approaches:

1. Acceptance by Final State: The PDA is said to accept its input by the final state if it enters any final state in zero or more moves after reading the entire input.

Let P =(Q, âˆ‘, Î“, Î´, q0, Z, F) be a PDA. The language acceptable by the final state can be defined as:

2. Acceptance by Empty Stack: On reading the input string from the initial configuration for some PDA, the stack of PDA gets empty.

Let P =(Q, âˆ‘, Î“, Î´, q0, Z, F) be a PDA. The language acceptable by empty stack can be defined as:

Equivalence of Acceptance by Final State and Empty Stack

• If L = N(P1) for some PDA P1, then there is a PDA P2 such that L = L(P2). That means the language accepted by empty stack PDA will also be accepted by final state PDA.
• If there is a language L = L (P1) for some PDA P1 then there is a PDA P2 such that L = N(P2). That means language accepted by final state PDA is also acceptable by empty stack PDA.

Example:

Construct a PDA that accepts the language L over {0, 1} by empty stack which accepts all the string of 0â€™s and 1â€™s in which a number of 0â€™s are twice of number of 1â€™s.

Solution:

There are two parts for designing this PDA:

• If 1 comes before any 0â€™s
• If 0 comes before any 1â€™s.

We are going to design the first part i.e. 1 comes before 0â€™s. The logic is that read single 1 and push two 1â€™s onto the stack. Thereafter on reading two 0â€™s, POP two 1â€™s from the stack. The Î´ can be

Now, consider the second part i.e. if 0 comes before 1â€™s. The logic is that read first 0, push it onto the stack and change state from q0 to q1. [Note that state q1 indicates that first 0 is read and still second 0 has yet to read].

Being in q1, if 1 is encountered then POP 0. Being in q1, if 0 is read then simply read that second 0 and move ahead. The Î´ will be:

Now, summarize the complete PDA for given L is: