snippetMinor
How to prove that sequences of stack operations are not context-free
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 ?
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.