Language Accepted By a Push Down Automata

 

Definition: Language Accepted by a Pushdown Automata

Let

$$M = (Q, \Sigma, \Gamma, \delta, q_0, z, F)$$

be a nondeterministic pushdown automaton (NPDA), where:

• $Q$: set of states

• $\Sigma$: input alphabet

• $\Gamma$: stack alphabet

• $\delta$: transition function

• $q_0 \in Q$: initial state

• $z \in \Gamma$: initial stack symbol (bottom-of-stack marker)

• $F \subseteq Q$: set of final states

---

Language Accepted by Final State

The language accepted by M is defined as:

$$L(M) = \{ w \in \Sigma^* \;|\; (q_0, w, z) \vdash^* (q, \varepsilon, u), \; q \in F, u \in \Gamma^* \}$$

---

Explanation (in words)

• Start in initial configuration:

  • State = $q_0$

  • Input = entire string $w$
    

  • Stack = just the start symbol $z$
    

• Apply transitions according to $\delta$, consuming input and modifying the stack.

• If, after reading all input symbols ($\varepsilon$ left), the automaton is in a final state ($q \in F$), then w is accepted.

• The final stack content u does not matter (it can be empty or non-empty).

---

Important Point

• This definition of acceptance is called acceptance by final state.

• There is another notion: acceptance by empty stack, where a string is accepted if the stack becomes empty (regardless of final state).

• Peter Linz later proves that both definitions are equivalent: every language accepted by empty stack can also be accepted by final state and vice versa.

A PDA accepts a string if it can consume the entire input and enter a final state. The remaining stack content does not matter in this definition.

Example:

1. The Problem

We want to construct an NPDA for the language:

$$L = \{ w \in \{a,b\}^* \;|\; \#a(w) = \#b(w) \}$$

That is, the set of all strings with the same number of a’s and b’s, regardless of order.
Examples:

• Accepted: ab, ba, aabb, abab, baab, …

• Not accepted: aab, bba, aaabb, …

---

2. Why Finite Automata Fail

A finite automaton cannot solve this, because it needs to count arbitrarily many a’s and b’s, which requires unbounded memory.
So, we use a pushdown automaton (NPDA) with a stack.

---

3. The Idea of the NPDA

We use the stack as a counter, with two different stack symbols:

• 0 → represents one unmatched a.

• 1 → represents one unmatched b.

Rules:

1. When we see an a:

   • If there’s a 1 on top (an unmatched b waiting), pop it.

   • Otherwise, push a 0 (record an unmatched a).

2. When we see a b:

   • If there’s a 0 on top (an unmatched a waiting), pop it.

   • Otherwise, push a 1 (record an unmatched b).

At the end:

• If all a’s and b’s are matched, the stack returns to bottom marker Z₀.

• If input finished and stack has only Z₀, accept.

---

4. Transition Graph 

• States:

  • q0 = start and processing state

  • qf = accepting state

• Transitions (informal):

  • On a with top Z → push 0Z

  • On a with top 0 → push another 0

  • On a with top 1 → pop the 1

  • On b with top Z → push 1Z

  • On b with top 1 → push another 1

  • On b with top 0 → pop the 0

  • On ε, with top Z → move to qf

---

5. Example Run: Input = baab

Let’s trace step by step:

Initial config: (q0, baab, Z)

1. Read b: top is Z → push 1 → (q0, aab, 1Z)

2. Read a: top is 1 → pop 1 → (q0, ab, Z)

3. Read a: top is Z → push 0 → (q0, b, 0Z)

4. Read b: top is 0 → pop 0 → (q0, ε, Z)

5. Input finished, stack = Z → ε-move to accept.

✅ baab is accepted.