2

Let $G=(V,T,P,S)$ be a context-free grammar without $\epsilon$ rules. Define a context-free grammar $G'$ which creates a language which consists of all words from $L(G)$ without one of the letters of a word which belongs to $L(G)$. For example, if $ab\in L(G)$ then $a\in L(G')$ and $b\in L(G')$.

The solution to the problem is as follows:

Let $G'=(V\cup V', T,P',S')$. $$ \forall (A\to \alpha)\in P\implies (A\to \alpha)\in P'\\ \forall (A\to \alpha B\gamma)\in P, B\in V\implies (A\to \alpha B\gamma)\in P'\\ \forall (A\to \alpha t\gamma)\in P, t\in T\implies (A\to \alpha\gamma)\in P' $$

Why $\forall (A\to \alpha B\gamma)\in P'$, because $\alpha, \gamma$ are strings of stack symbols (not just letters) hence they cannot be divided (like for example, $\forall (A\to \alpha B\gamma)\in P, B\in V\implies (A\to \alpha)\in P'\quad\land\quad (A\to \gamma)\in P'$)?

Yos
  • 2,663
  • 1
    I’m afraid I don’t understand what you are asking, but it may help to know there are some typos in the solution as written. The RHS is the second line should be $(A’ \to \alpha B’ \gamma) \in P’$ and the RHS in the third line should be $(A’\to \alpha\gamma) \in P’$. – Erick Wong Dec 24 '18 at 02:51

2 Answers2

1

In your solution you missed some essential primes.

The idea is that the new grammar is just as the original one, except that it loses one of the generated symbols. But it should be clear that there is exactly one terminal that disappears. The primed symbol has the "task" of (not) generating that disappearing terminal. It hands this task to one of its successors.

Axiom $S'$, just like $S$, but remember a symbol has to be deleted in the derivation that follows.

If $A\to \alpha\in P$ then $A\to \alpha\in P'$ (Unprimed symbols behave as before.)

If $A\to \alpha B\gamma\in P$ then $A'\to \alpha B' \gamma\in P'$ (The task is delegated to a successor)

If $A\to \alpha t\gamma\in P$ ($t$ terminal) then $A'\to \alpha \gamma\in P'$ (no more primes, terminal was deleted)

Hendrik Jan
  • 1,910
  • I have a similar question here maybe it will interest you as well https://math.stackexchange.com/questions/3085897/how-to-transition-from-context-free-grammar-g-to-to-context-free-grammar-which – Yos Jan 24 '19 at 13:49
0

Thanks for the post, stuck with the same problem. Yos, I think that in your question you mess grammar and pushdown automata representation (which has stack). In this case, I think that in the solution you've published, α,γ∈$\bigl((V∪V′)∪T\bigr)^\ast$. I'd be glad if anyone could approve that.
As for me, from the given notation, it is still unclear when the transmission from V to V' variables happens.

griko
  • 1