A pushdown automaton accepts a^n b^n but none accepts a^n b^n c^n; why does one stack stop there?

seniormust knowfreq 52%

answer

one store, one live count
the pops consume the record
the finite control cannot hold n
moving the pairing moves the hole
nesting works, crossing does not

basics

~20 s

One stack holds one live count and spending it destroys it. Matching the b's pops away the record of how many a's there were, so nothing remains to check the c's against, and two independent matched counts are beyond the model.

solid answer

~50 s

For a^n b^n the machine pushes one symbol per a, then pops one per b, and an exhausted store means the two blocks matched. The trouble is that the pops consumed the record: after the b's, the value of n exists nowhere - not in the store, which is empty, and not in the control, which is finite and cannot hold a quantity that grows with input. Swapping the pairing does not help, because whichever two blocks you match, the third has nothing to verify against and the input is read once, left to right. The shape of the argument that no such machine exists is that repetition inside an accepted word touches at most two stretches at a time, and two stretches cannot cover three blocks. In a frame format this is the rule that a single-store reader enforces one count relationship per pass.

For `a^n b^n` the machine pushes one symbol per `a`, then pops one per `b`, and an exhausted store means the two blocks matched. The trouble is that the pops **consumed** the record: after the b's, the value of `n` exists nowhere - not in the store, which is empty, and not in the control, which is finite and cannot hold a quantity that grows with input. Swapping the pairing does not help, because whichever two blocks you match, the third has nothing to verify against and the input is read once, left to right. The shape of the argument that no such machine exists is that repetition inside an accepted word touches at most two stretches at a time, and two stretches cannot cover three blocks. In a frame format this is the rule that a single-store reader enforces **one** count relationship per pass.

code

pseudocode · 11 lines

pseudocode

# accepts a^n b^n, then has nothing left for c^n
while next symbol is 'a':
    push(MARK)
while next symbol is 'b':
    if store is empty:
        reject                # more b's than a's
    pop()
# store is now empty and the control is one of finitely many states:
# the value of n exists nowhere
while next symbol is 'c':
    ???                       # no marker left to compare against

go deeper

for a junior

Recall the two-block case: push one marker per symbol in the first block, pop one per symbol in the second, and an empty store at the end means the counts matched.

for a middle

Explain that the pops destroy the count, so after matching two blocks nothing records the number. Say why the finite control cannot hold it either.

for a senior

Recognise the pattern in a real validation rule: a second unbounded count means the streaming reader is finished and you are choosing between a stronger machine, a buffered second pass, or a format change.

for a principal

The lead's move is to spot the requirement before it is written into a format, because a rule that needs two matched counts converts every reader in the ecosystem from streaming to buffering.

This is the boundary question for the model, and the canonical way an interviewer finds out whether a candidate understands the store or has only memorised that it 'counts things'.

The run that works

For a^n b^n the machine has an easy job:

While the input symbol is a, push one marker per symbol. Depth now equals the number of a's seen.
On the first b, switch phase. For each b, pop one marker; a b arriving on an empty store means there were more b's than a's.
At end of input, an exhausted store means the counts matched exactly.

Nothing here requires guessing: the switch is forced by the change of input symbol, so even a machine with one move per configuration handles it.

Why a third block has nothing to check against

At the moment the last b is consumed, look at what the machine holds. The store is empty. The control is in one of finitely many states, chosen when the machine was built, so it cannot be holding a number that grows with the input. The quantity n is simply gone. When the c's arrive, there is nothing to compare them to, and the machine can do no better than count them up to a fixed bound and then accept anything.

Re-ordering the work moves the hole without closing it. Match the b's against the c's instead, and the a's went unchecked. Push two markers per a and pop one per b and one per c, and the order defeats you: the markers interleave in one last-in-first-out sequence and cannot be drawn off in two separate runs.

The idea of the impossibility argument

A candidate should not attempt the proof aloud, but should be able to give its shape: any sufficiently long accepted word contains structure that can be repeated, and the repetition affects at most two stretches of the word simultaneously. In a three-block word, two stretches cannot touch all three blocks, so repeating them produces a word whose blocks no longer have equal counts - a word the language does not contain, but which the machine would accept. That contradiction is what rules the language out.

Nearby languages that are still within reach

The distinguishing property is nesting versus crossing dependencies.

language	within reach of one store?	why
`a^n b^n`	yes	one matched pair, checked in one phase
`a^n b^n c^m`	yes	match the first two blocks, then consume the rest freely
`a^n b^m c^n`	yes	push the a's, let the b's pass untouched, pop on the c's
`a^n b^n c^n`	no	two independent matched counts
`a^n b^m c^n d^m`	no	the dependencies cross rather than nest

The third row surprises people: the matched blocks are not adjacent, yet the machine copes, because the unmatched middle block can be skipped while the markers sit undisturbed. The last row is the general statement of the limit - a store matches things that nest inside one another, and fails on things that interleave.

What this means for a reader you might actually write

Suppose a frame declares a count in its header, repeats it implicitly in the body, and states it again in a trailer. A single-store reader can enforce one of those two pairings in a streaming pass. Enforcing the other requires something the model does not have:

an extra counter kept outside the store, which is a different machine;
a second pass, which needs the input buffered and so costs memory proportional to the frame;
or a format change that makes the third check unnecessary, such as deriving the trailer count from what the reader already matched.

The engineering habit worth taking away is to notice when a validation rule quietly asks for a second unbounded count. That is the moment a streaming validator turns into a buffering one, and the cost shows up as memory rather than as a broken test.

Common wrong turns

'Use a bigger stack.' Size is not the constraint; the model's store is already unbounded. The constraint is that a popped symbol is gone and only one count can be live.
'Let the machine guess.' Guessing does not help here at all: the language is outside the class for machines that guess as well.
'Re-read the a's.' The input is consumed once, left to right. A machine that may rewind is a different model.

This is the boundary question for the model, and the canonical way an interviewer finds out whether a candidate understands the store or has only memorised that it 'counts things'. ## The run that works For `a^n b^n` the machine has an easy job: 1. While the input symbol is `a`, push one marker per symbol. Depth now equals the number of a's seen. 2. On the first `b`, switch phase. For each `b`, pop one marker; a `b` arriving on an empty store means there were more b's than a's. 3. At end of input, an exhausted store means the counts matched exactly. Nothing here requires guessing: the switch is forced by the change of input symbol, so even a machine with one move per configuration handles it. ## Why a third block has nothing to check against At the moment the last `b` is consumed, look at what the machine holds. The store is empty. The control is in one of finitely many states, chosen when the machine was built, so it cannot be holding a number that grows with the input. The quantity `n` is simply gone. When the c's arrive, there is nothing to compare them to, and the machine can do no better than count them up to a fixed bound and then accept anything. Re-ordering the work moves the hole without closing it. Match the b's against the c's instead, and the a's went unchecked. Push two markers per `a` and pop one per `b` and one per `c`, and the order defeats you: the markers interleave in one last-in-first-out sequence and cannot be drawn off in two separate runs. ## The idea of the impossibility argument A candidate should not attempt the proof aloud, but should be able to give its shape: any sufficiently long accepted word contains structure that can be repeated, and the repetition affects **at most two** stretches of the word simultaneously. In a three-block word, two stretches cannot touch all three blocks, so repeating them produces a word whose blocks no longer have equal counts - a word the language does not contain, but which the machine would accept. That contradiction is what rules the language out. ## Nearby languages that are still within reach The distinguishing property is **nesting** versus **crossing** dependencies. | language | within reach of one store? | why | |---|---|---| | `a^n b^n` | yes | one matched pair, checked in one phase | | `a^n b^n c^m` | yes | match the first two blocks, then consume the rest freely | | `a^n b^m c^n` | yes | push the a's, let the b's pass untouched, pop on the c's | | `a^n b^n c^n` | no | two independent matched counts | | `a^n b^m c^n d^m` | no | the dependencies cross rather than nest | The third row surprises people: the matched blocks are not adjacent, yet the machine copes, because the unmatched middle block can be skipped while the markers sit undisturbed. The last row is the general statement of the limit - a store matches things that nest inside one another, and fails on things that interleave. ## What this means for a reader you might actually write Suppose a frame declares a count in its header, repeats it implicitly in the body, and states it again in a trailer. A single-store reader can enforce **one** of those two pairings in a streaming pass. Enforcing the other requires something the model does not have: - an extra counter kept outside the store, which is a different machine; - a second pass, which needs the input buffered and so costs memory proportional to the frame; - or a format change that makes the third check unnecessary, such as deriving the trailer count from what the reader already matched. The engineering habit worth taking away is to notice when a validation rule quietly asks for a second unbounded count. That is the moment a streaming validator turns into a buffering one, and the cost shows up as memory rather than as a broken test. ## Common wrong turns - **'Use a bigger stack.'** Size is not the constraint; the model's store is already unbounded. The constraint is that a popped symbol is gone and only one count can be live. - **'Let the machine guess.'** Guessing does not help here at all: the language is outside the class for machines that guess as well. - **'Re-read the a's.'** The input is consumed once, left to right. A machine that may rewind is a different model.

Could the machine match the b's against the c's and check the a's afterwards?
It can, and then the a's are the unchecked block. Whichever pairing the store is spent on, the remaining block has nothing to verify against, because a popped symbol is gone and the input is read once from left to right. Changing which two blocks are matched relocates the hole rather than closing it.
Which three-block languages are still within reach of one store?
Those whose matched blocks nest rather than cross. `a^n b^n c^m` works by matching the first two blocks and then consuming the rest, and `a^n b^m c^n` works by pushing the a's, letting the b's pass, and popping on the c's. A language such as `a^n b^m c^n d^m`, where the two dependencies interleave, is out.
Would allowing the machine to guess bring the three-block language within reach?
No. The language sits outside the class for guessing machines too, so this is not a determinism question. The limit is the single store, and guessing changes only which languages inside that class a forced-move machine can reach.
What does a validator do when a rule needs a second unbounded count?
It stops being a streaming reader. Either it keeps a counter outside the store, which is a stronger machine, or it buffers the input and makes a second pass, which costs memory proportional to the frame. Recognising that moment early is what keeps a validator's memory profile predictable.

saying these in an interview costs you the question

Says a bigger or faster stack would handle three matched counts
Claims the machine can re-read the a's after the b's are consumed
Thinks a^n b^m c^n is out of reach because the matched blocks are not adjacent
Says guessing would let one machine check all three counts
Believes the finite control can hold a count that grows with input
Treats one matched pair and three matched blocks as the same problem

A pushdown automaton accepts a^n b^n but none accepts a^n b^n c^n; why does one stack stop there?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The run that works

Why a third block has nothing to check against

The idea of the impossibility argument

Nearby languages that are still within reach

What this means for a reader you might actually write

Common wrong turns

▾common follow-ups4 questions

▾red flags6 flags

The run that works

Why a third block has nothing to check against

The idea of the impossibility argument

Nearby languages that are still within reach

What this means for a reader you might actually write

Common wrong turns

answer

go deeper