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.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Can a Backspace erase a nonterminal, too? $\endgroup$– reinierpostJul 25, 2022 at 9:55
-
$\begingroup$ @reinierpost It seems natural that the backspace can only be applied on the resulting terminal string. In that way the order of derivation steps does not matter. For a given derivation tree there is generated string with backspaces, which is then "interpreted" to a normal string. $\endgroup$– Hendrik JanJul 25, 2022 at 14:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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{<BKSP>}$ 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.
-
3$\begingroup$ My interpretation of the question is different: "given a CFG with backspace, can we find an ordinary CFG with the same language". My problem is that the Dyck structure of the backspaces is not necessarily the structure in the grammar. A backspace can delete a symbol in a neighbouring subtree. I could not find an example where a backspace-CFL gave a non-CF language. $\endgroup$ Jul 25, 2022 at 8:55
-
$\begingroup$ @HendrikJan: perhaps the question is not optimally worded, but it does say "if we add backspace…, are the languages produced still context-free", for which I think the natural interpretation is the one I chose: "can we add a symbol-deleting backspace to a CFL?" Your question is also interesting, but I strongly suspect it has the same answer. $\endgroup$– riciJul 25, 2022 at 15:07
-
$\begingroup$ @HendrikJan's interpretation is what I meant. I thought your answer addressed that but I guess I didn't fully understand it. $\endgroup$ Jul 25, 2022 at 19:00
-
$\begingroup$ @user126100: so you have a context-free grammar which generates a language including backspaces? Care to show an example? (In fact, I do think my answer covers both directions but the formal proof is not so simple.) $\endgroup$– riciJul 25, 2022 at 19:48