Course contentsShow
← Computer Science
Lesson 1833 of 2,87241. Context-Free LanguagesFree lesson

Designing PDAs for Simple Languages

Constructing PDAs for languages like {0^n 1^n | n≥0} using stack to count and match symbols.

Designing PDAs for Simple Languages

You'll learn how to construct a pushdown automaton that recognizes the language {0^n 1^n | n≥0} by using the stack to count and match symbols.

The Core Idea

Imagine you're a parking attendant counting cars entering and leaving a garage. You make a tally mark for each car that enters, then cross one off for each car that exits. If your marks all cancel out perfectly, you know the same number entered and left.

A PDA does exactly this for matching symbols! For the language {0^n 1^n | n≥0}, we need strings like ε, 01, 0011, 000111, etc.—always the same number of 0s followed by the same number of 1s.

Construction Strategy

Phase 1: Push zeros
As you read each 0 from the input, push a symbol (say Z) onto the stack. This "counts" how many 0s you've seen.

Phase 2: Pop for ones
When you encounter the first 1, transition to a new state. For each 1 you read, pop one symbol from the stack. This matches each 1 against a previously-seen 0.

Phase 3: Verify completion
Accept if you've consumed all input and the stack is empty (or you reach a final state with an empty stack).

Example Trace

For input 0011:

  • Read 0: push Z → stack: [Z]
  • Read 0: push Z → stack: [Z, Z]
  • Read 1: pop Z → stack: [Z]
  • Read 1: pop Z → stack: []
  • Input exhausted, stack empty → Accept

Key Takeaway: Design PDAs for simple context-free languages by using the stack as a counter—push symbols to remember occurrences, then pop to match and verify balance.