Membership problem for certain class of unrestricted grammars 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)$?
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.