Pushdown Automata for Strings With b Exactly in the Middle

⭐ Pushdown Automata for Strings With ‘b’ Exactly in the Middle

Imagine a string where the letter b sits right at the center, and the letters on both sides must match in a very strict way. A common pattern for this is:

L = { aⁿ b aⁿ | n ≥ 0 }

This simply means:

• some number of a’s on the left,
• exactly one b in the center,
• and the same number of a’s on the right.

A few valid strings look like:

• b
• a b a
• aa b aa
• aaa b aaa

Wrong examples:

• ab (not balanced)
• ba (not balanced)
• aabaaa (no b in center)
• aabbbaa (multiple b’s)

So the middle b is like a dividing line between two mirror halves.

---

⭐ Why a PDA Can Recognize This Language

A normal finite automaton has no memory.
It cannot “remember” how many a’s appeared before the b.

But a PDA can, because it has a stack.

The stack acts like a simple memory:

• Before the b:
  every time the machine reads a, it pushes a symbol (say A) onto the stack.
• After the b:
  every time it reads a, it pops an A.

If every pushed symbol is popped by the time the input ends, the string is correct.

If the popping doesn’t match the pushing, the machine rejects.

---

⭐ How the PDA Works (Intuition)

To make things easy, picture the PDA working in two modes:

Mode 1: Before the middle b

• Machine reads a
• For each a, it puts one marker (A) on the stack
• Stack grows: A, AA, AAA…

When it finally encounters the first b, the machine switches to the second mode.

---

Mode 2: After reading ‘b’

• Machine now expects the same number of a’s
• For each a, it removes one A from the stack
• If stack empties neatly at the end, accept the string

If anything goes wrong, such as:

• extra a’s after b
• fewer a’s after b
• more than one b
• the stack empties too early
  → the PDA rejects the input.

---

⭐ Simple ASCII Diagram of the PDA

          (push A for each 'a' before b)
       +------------------------------+
       |                              |
       |        a, Z → A Z            |
       |        a, A → A A            |
       v                              |
   +-----------+      b, A → A     +-----------+
   |    q0     | ----------------> |    q1     |
   +-----------+                   +-----------+
           ^                             |
           |                             |
           |      a, A → ε  (pop A)      |
           +------------------------------+
                               |
                               |  Z → Z   (final check)
                               v
                         +-----------+
                         |   q2      |
                         | (accept)  |
                         +-----------+

• q0: counting a’s before the b
• q1: matching a’s after the b using pops
• q2: accept state when only the bottom symbol Z remains

---

⭐ Example Walkthrough

Let’s test the string:

aaa b aaa

Before b:

• Read a → push A
• Read a → push A
• Read a → push A
  Stack: AAAZ

Read b:

• Move to popping mode (q1)

After b:

• Read a → pop A
• Read a → pop A
• Read a → pop A
  Stack: Z

Input finished → Accept

Everything matched perfectly.

---

⭐ In Plain Words

Think of it like stacking coins before reaching b, and then removing those coins one by one after b.
If the number of coins removed exactly equals the number of coins added, the machine is happy and accepts the string.

---

About the Author

examhopeinfo@gmail.com

Administrator

Visit Website View All Posts