# Automata PDA Acceptance

Automata PDA Acceptance with automata tutorial, finite automata, dfa, nfa, regexp, transition diagram in automata, transition table, theory of automata, examples of dfa, minimization of dfa, non deterministic finite automata, etc.

# 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:

```L(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ F}
```

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:

```N(PDA) = {w | (q0, w, Z) ⊢* (p, ε, ε), q ∈ Q}
```

### 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

```δ(q0, 1, Z) = (q0, 11, Z)        Here Z represents that stack is empty
δ(q0, 0, 1) = (q0, ε)
```

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:

```δ(q0, 0, Z) = (q1, 0Z)
δ(q1, 0, 0) = (q1, 0)
δ(q1, 0, Z) = (q0, ε)        (indicate that one 0 and one 1 is already read, so simply read the second 0)
δ(q1, 1, 0) = (q1, ε)
```

Now, summarize the complete PDA for given L is:

```δ(q0, 1, Z) = (q0, 11Z)
δ(q0, 0, 1) = (q1, ε)
δ(q0, 0, Z) = (q1, 0Z)
δ(q1, 0, 0) = (q1, 0)
δ(q1, 0, Z) = (q0, ε)
δ(q0, ε, Z) = (q0, ε)      ACCEPT state
```