HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

How to prove that sequences of stack operations are not context-free

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
operationsstackfreeareprovethathowcontextnotsequences

Problem

By stack I mean the language of sequences it represents, say, a stack with data domains $N$ (natural number) is: $\{ \mbox{push(0)}, \mbox{push(1)}, \mbox{push(0).push(1)}, ..., \mbox{push(0).pop(0)}, ...\}$.

This language is not against Pump lemma of CFL, right ? But I read from some materials that this language is NOT context-free. So why is that ?

Solution

The language is context-free. If we replace $\mathrm{push}(k)$ by $[_k$ and $\mathrm{pop}(k)$ by $]_k$ and delete the dots, then we get exactly all prefixes of a Dyck language with $N$ different types of brackets.

Context

StackExchange Computer Science Q#60678, answer score: 6

Revisions (0)

No revisions yet.