Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 59 ยท Pushdown Automata

PDAs for Either/Or Conditions and Equal Counts

Build nondeterministic PDAs that guess which condition holds (i=k or j=l, i=j or j=k) and a one-state PDA for strings with equally many a's and b's.

Two more patterns finish the toolkit for exam-style PDA constructions. The first is either/or: the string is in the language if one of two conditions holds, such as i = k or j = l. A nondeterministic PDA handles this by guessing which condition applies and running a separate machine for each guess. The second is equal counts in any order: strings over {a, b} with as many as as bs, where the symbols may be mixed freely.

Either/or: guess a branch

Take L = { a^i b^j c^k d^l : i = k or j = l, with i, j, k, l โ‰ฅ 1 }. A union of two languages is a union of two machines:

  • Branch U checks i = k: push on a, leave the stack alone on b, pop on c, then ignore d.
  • Branch V checks j = l: ignore a, push on b, leave the stack alone on c, pop on d.

The machine starts with an ฮต-move into one of the two branches. It accepts if either branch accepts.

flowchart LR
    S(["q0"]) -->|"ฮต, $ / $"| U0["branch U<br/>a: push, b: skip,<br/>c: pop, d: skip"]
    S -->|"ฮต, $ / $"| V0["branch V<br/>a: skip, b: push,<br/>c: skip, d: pop"]
    U0 --> F((("accept")))
    V0 --> F

Nondeterminism lets the PDA run both checks in parallel; a string is accepted if at least one succeeds.

Python a^i b^j c^k d^l with i = k or j = l

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In branch U the transition ("u2", "b", "A", "u2", "A") pops and pushes the same symbol, which keeps the stack unchanged while the bs are read. The string aabccd is accepted by branch U (i = k = 2), aabbcdd only by branch V (i = 2 โ‰  k = 1, but j = l = 2), and aabbbcd by neither.

The three-block cousin L = { 0^i 1^j 2^k : i = j or j = k, i, j, k โ‰ฅ 1 } has the same structure: branch one pushes zeros, pops ones, ignores twos; branch two ignores zeros, pushes ones, pops twos.

Python 0^i 1^j 2^k with i = j or j = k

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Equal counts in any order

Let L = { w โˆˆ {a, b}* : w has equally many a's and b's }. The as and bs can be interleaved arbitrarily, so no phases are needed. The trick is to let the stack hold the surplus: if more as than bs have been read so far, the stack holds one A per unmatched a; if more bs, one B per unmatched b. A new symbol either cancels a marker of the opposite kind or adds a marker of its own kind.

Top of stack Read a Read b
$ (balanced) push A push B
A (surplus of a) push another A pop A
B (surplus of b) pop B push another B

At the end, accept if the stack is back to $. One state is enough, plus an accepting state reached by ฮต, $ / $.

Python Equal numbers of a's and b's

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

All reading moves are deterministic. Strictly speaking the machine is not a DPDA, because the final ฮต-move competes with the reading moves when $ is on top; adding an end-of-input marker removes that conflict. The language is a deterministic context-free language.

The same idea counts differences in other ratios. For "twice as many as as bs" the stack records a weighted surplus; the design is longer but follows the same table logic. Related: the grammar S โ†’ aSbS | bSaS | ฮต generates this language.

A checklist for new languages

  1. Find the constraints. Is it an equality between blocks, a sum, or an either/or?
  2. Equalities need push-then-pop. Sums use one marker for both. Either/or is a nondeterministic union.
  3. Order constraints (a*b*c*) go into the states; count constraints go into the stack.
  4. Mixed orders (any interleaving) use a surplus counter like the table above.
  5. Verify with agrees(...) against a predicate, and add the empty string deliberately if it is in the language.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How does a PDA recognize a language defined by 'condition A or condition B'?

    Nondeterminism lets the PDA explore both checkers in parallel; acceptance by any branch is enough.
  2. 2. In the equal a's and b's machine, what does a stack with two A's mean?

    The stack records the surplus: a's not yet cancelled by b's.
  3. 3. In branch U of the i = k or j = l machine, what happens while the b's are read?

    That branch checks only i = k, so the b block is just skipped while the markers wait for the c's.
  4. 4. Which language is NOT context-free, so no PDA can recognize it?

    Checking two equalities at once (a's = b's and b's = c's) needs the count of b's to be used twice, but popping destroys it.

Summary

  • Either/or conditions are unions: guess the branch with an ฮต-move, then run the matching checker.
  • Skipping a block means reading it while leaving the stack as it is.
  • Equal counts in any order are tracked by a surplus counter: push the same kind, pop the opposite kind.
  • Order of blocks lives in the states; quantities live in the stack.

Next: PDAs for palindromes