Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 59 ยท Pushdown Automata

PDAs for Sums of Counts: a^m b^n c^(m+n) and More

Design PDAs where one block equals the sum of others: a^m b^n c^(m+n), a^m b^(m+n) c^n, 0^n 1^m 2^m 3^n, m+n=p+q and a^2m c^4n d^n b^m, tested in Python.

In the last lesson one block was compared with another. Here a block must match the sum of two others, or blocks nest inside each other. Stacks handle both situations because they are last in, first out: the symbols pushed last are the first to be matched.

Two ideas cover almost every exam question in this family:

  • Additive counts (m + n = p): all markers can live on the stack together, because the stack does not care which block produced a marker, only how many there are.
  • Nested counts (0^n 1^m 2^m 3^n): use different marker symbols for different blocks, so that the inner block is matched first and the outer block last.

Same marker, add the counts

Push twice Blocks a and b both push the same marker.
Pop once Block c pops one marker per symbol.

a^m b^n c^(m+n) and 0^n 1^m 2^(n+m).

1 / 2

Additive counts

a^m b^n c^{m+n} (m, n โ‰ฅ 1). Push A on every a and on every b. Pop one A per c. Accept when only $ remains. The stack never records which symbol produced a marker, which is exactly what we want.

a^m b^{m+n} c^n (m, n โ‰ฅ 1). Now the b block is the sum. The first m bs must be matched against the as (pop), and the remaining n bs must be remembered for the cs (push). The machine decides to switch from popping to pushing when the stack shows only $, so it uses the bottom marker as a signal: b, $ / A$ starts the pushing phase.

0^n 1^m 2^{n+m} (m, n โ‰ฅ 0). Same stack symbol for 0s and 1s, pop on 2s. Because m and n may be zero, phases may be empty: use ฮต-moves to jump to the next phase from any stack top.

Python Three additive machines

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 S2 the move ("q1", "b", "$", "q2", "A$") is the heart of the design: the stack is now back to $, so the as are all matched, and the next b is one of the extra n.

Sums on both sides: m + n = p + q

For a^m b^n c^p d^q with m + n = p + q and all exponents at least 1, only the total matters. Push a marker for each a and b; pop a marker for each c and d; accept at $. The order constraint a* b* c* d* is enforced by the states: four phases, each one a loop.

Python m + n = p + q

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.

Notice that "abccd" is rejected: a+b = 2 but c+d = 3. Also aabcdd is accepted: 2+1 = 1+2.

Nested counts with different markers

0^n 1^m 2^m 3^n (m, n โ‰ฅ 0). The 1s and 2s match as an inner pair, the 0s and 3s as an outer pair. Use X for zeros and Y for ones. Pushing Ys on top of Xs means the 2s see Y first, and the 3s see Xs after all Ys are gone.

a^{2m} c^{4n} d^n b^m (m, n โ‰ฅ 0). Same nesting, with fractions: one marker B per two as (an even/odd state toggles), one marker D per four cs (a counter state mod 4). Then d pops D, b pops B. Writing the rule table by hand would be long, so we generate it with loops.

Python Nested blocks and fractional counts

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.

The generated table has one rule per top symbol, because the PDA must be able to start a phase no matter what is currently on top. Both machines are checked against regular-expression predicates; empty lists mean they agree everywhere.

Fractions like a^{2m} do not need more stack: a state can count modulo 2 or 4. The stack only counts the quotient.

Why these are all context-free

Every language here has a grammar that mirrors the nesting. For example 0^n 1^m 2^m 3^n is generated by S โ†’ 0 S 3 | T and T โ†’ 1 T 2 | ฮต, and a^m b^n c^{m+n} by S โ†’ a S c | T and T โ†’ b T c | b c, with a little care for the lower bounds. A language is not context-free when two independent counts must be compared with a third, such as a^n b^n c^n (see context-sensitive grammars).

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which stack discipline recognizes a^m b^n c^(m+n)?

    The c block must match the total of the a's and b's; both earlier blocks contribute markers and c pays them back.
  2. 2. In the PDA for a^m b^(m+n) c^n, why is the transition b, $ / A$ important?

    When $ is on top, all the a's have been matched by the first m b's, so remaining b's must be remembered.
  3. 3. Why does the machine for 0^n 1^m 2^m 3^n use two different marker symbols?

    Y markers sit above X markers, so the 2s pop Y first and then the 3s pop X.
  4. 4. How is one marker per four c's implemented in the a^2m c^4n d^n b^m machine?

    Finite counting (mod k) lives in the control states; the stack records the quotient.

Summary

  • For sums (m + n = p), use one marker symbol: all blocks push or pop the same kind of marker.
  • Use the bottom marker $ as a signal that a matched block has been fully paid back.
  • For nested blocks, use different markers so the innermost block is matched first.
  • Fractions such as 2m or 4n are handled by counting modulo k in the state.
  • Generate large rule tables with loops, then test against a predicate.

Next: PDAs for either/or conditions and equal counts