9
$\begingroup$

Consider an arbitrary context-free grammar $G$ over the alphabet $\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$. To the productions of this grammar, add two fixed non-context-free productions $P$: $\overline{0} 0 \rightarrow \epsilon$ and $\overline{1} 1 \rightarrow \epsilon$. Call the resulting grammar $G^P$ standing for "$G$ augmented with the productions $P$".

Is it possible to give an algorithm which takes a grammar $G^P$ and a string $s$ over $\lbrace 0,1,\overline{0} ,\overline{1} \rbrace$ and decides whether $s \in \mathcal{L}(G^ P)$?

Improve this question
$\endgroup$
2
  • $\begingroup$ Interestingly, while the answer seems to be "no", I think that if $L(G)$ is regular, then so is $L(G^P)$. Essentially, an NFA for $L(G)$ can be transformed into one for $L(G^P)$ by iteratively adding $\epsilon$-transitions $(s,\epsilon,t)$ whenever you have paths $(s,\bar{0},p,0,t),(s,\bar{0},p,\epsilon,q,0,t),(s,\bar{1},p,1,t),(s,\bar{1},p,\epsilon,q,1,t)$ or $(s,\epsilon,p,\epsilon,t)$, and finally performing $\epsilon$-elimination. $\endgroup$
    – Klaus Draeger
    Oct 2, 2014 at 12:29
  • $\begingroup$ Yes that is true. In fact, the question arose from a problem in program analysis (liveness based garbage collection). We circumvented the problem by approximating the CFG to a strongly regular grammar (Mohri-Nederhoff transformation), and then doing the $P$ simplifications on the resulting NFA in exactly the way Klaus Draeger mentions. $\endgroup$
    – Amit. S
    Oct 2, 2014 at 12:59

1 Answer 1

Reset to default
5
$\begingroup$

This class of grammars is undecidable. Here is a rough idea about how to use it to emulate Turing machines.

At each point, the current partially expanded word would look like

$$[\mbox{tape to the left}][\mbox{head}][\mbox{tape to the right}]$$

Here:

  • $[\mbox{tape to the left}]$, after applying $P$, only contains characters $\overline0$ and $\overline1$.
  • $[\mbox{tape to the right}]$, after applying $P$, only contains characters $0$ and $1$.
  • $[\mbox{head}]$ is a single nonterminal, which encodes both the head state and the character at the head position.

Suppose that the head is in state $S$, and the character under the head is $i\in\{0,1\}$. Then the head is represented by nonterminal $S_i$. If it needs to transition to state $T$, replace the current character with $j$, and move to the left, there are two transitions $S_i\rightarrow0T_0j$ and $S_i\rightarrow1T_1j$. If it needs to move to the right instead, there are two transitions $S_i\rightarrow\overline jT_0\overline0$ and $S_i\rightarrow\overline jT_1\overline 1$. In some sense, the head has to "guess" the character in the direction it is moving to by producing the matching character. If the guess is wrong, the invariant on $[\mbox{tape to the left}]$ or $[\mbox{tape to the right}]$ would be violated, and it would never recover.

When the machine halts, the head should "consume" its tape on both sides by "guessing" and producing matching characters. After that, it should produce empty word. As a result, empty word would be a member of such grammar if and only if the corresponding Turing machine halts.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I am not sure that I understand your reduction. Here is my doubt: If the given Turing machine has $N$ states, then isn't the number of unrestricted productions required to emulate the Turing machine related to $N$? But my problem allows just two fixed unrestricted productions. $\endgroup$
    – Amit. S
    Oct 2, 2014 at 13:41
  • $\begingroup$ @Amit.S I provided some more explanation of transitions in the answer. $\endgroup$
    – abacabadabacaba
    Oct 2, 2014 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.