patternMinor
What are the languages produced by context free-grammars with backspace?
Viewed 0 times
thewhatfreearelanguageswithgrammarsproducedbackspacecontext
Problem
If we add backspace to the output alphabet, are all the languages produced still context-free? (If not, then what are they?)
The word (a, b, c, Backspace, Backspace), for example, gets interpreted as a.
The word (a, b, c, Backspace, Backspace), for example, gets interpreted as a.
Solution
The language of a finite alphabet matched with backspaces is a Dyck language (i.e. it's equivalent to balanced parenthetic expressions); one grammar for it has the productions $L\to a_iL \text{}$ for every $a_i\in \Sigma$, as well as $L\to\epsilon$ and $L\to LL$.
So you can take any context-free grammar and transform it into a backspace-cancel equivalent by adding $L$ and new non-terminals $A_i$ for each $a_i\in \Sigma$, with productions $A_i\to a_i L$. Then replace every use of $a_i$ (other than in the productions for $L$) with $A_i$. Finally, add a new start production, $S'\to L S$.
The result will not be deterministic, of course, not even using a deterministic grammar for $L$. But it's certainly context-free.
So you can take any context-free grammar and transform it into a backspace-cancel equivalent by adding $L$ and new non-terminals $A_i$ for each $a_i\in \Sigma$, with productions $A_i\to a_i L$. Then replace every use of $a_i$ (other than in the productions for $L$) with $A_i$. Finally, add a new start production, $S'\to L S$.
The result will not be deterministic, of course, not even using a deterministic grammar for $L$. But it's certainly context-free.
Context
StackExchange Computer Science Q#153186, answer score: 4
Revisions (0)
No revisions yet.