0
$\begingroup$

Given a context-free grammar $G$ for a language $L$, where $L$ contains strings of length greater than 2, show that there exists some context-free grammar $G'$ which generates $L$ such that every rule of $G'$ has the form $$A\to x_1 x_2$$

where $x_i$ is either a terminal or non-terminal and $A$ is a terminal.

I know that this CFG $G'$ has to be similar to the CNF of $G$.

However, I am unsure how to remove transitions of the form $A\to a$. If $A$ is the start state of $G$, then it produces a string of length $1$, which would not be allowed. But what about the case when $A$ is not a start state?

$\endgroup$

1 Answer 1

0
$\begingroup$

The solution is to "substitute" the terminal rules into the binary rules.

Start with a grammar in Chomsky normalform. Then for every pair of rules $A\to BC$ and $B\to a$ we add the rule $A\to aC$.

This is only one of the possible combinations. Also substitute the right nonterminal, or both of them. Now keep all binary rules (old and new ones) and delete all the original terminal rules $A\to a$.

If we compare the derivation trees of the new grammar with those of the original grammar, we see that all terminals are moved one level up as a consequence of the substitutions.

$\endgroup$

Your Answer

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

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