Given context-free grammar $G$ whose terminal letters are $\{a,b,c,d\}$ how can we transition to context-free grammar which contains the words from the language that $G$ creates but which start with $a$ and end with $d$?

I guess we could create new production rules where for example $A\to aX$ from $G$ would also be in $G'$ but how can we determine whether a production rule for middle state come from some rule which starts with $a$ and eventually end with $d$?


1 Answer 1


Note that with the constuction from the question "How to define a grammar which creates a language from words of another grammar without one of the letters?" you see how messengers can be sent inside the derivation (or derivation tree) to perform certain actions or to check certain properties of the tree.

In your case there are two such actions: (1) the first symbol should be an $a$ (2) the last symbol should be a $d$. This calls for two markers, or in other words two new copies of each of the nonterminals. The first and last symbols of the derivation $A_f$ and $A_\ell$.

If $A\to \alpha $ is in the original set of productions $P$ then it is also in the new set $P'$. For the new copy $A_f$ we have cases to consider. If $\alpha$ starts with $a$, so $\alpha =a\beta$ then $A_f\to a\beta$ is in $P'$. Also, when $\alpha$ starts with a nonterminal, so $\alpha=B\beta$, then we get $A_f\to B_f\alpha$ in $P'$.

Similarly for the final letter $d$ and variables $A_\ell$. Finally the construction is complicated by the fact that initially the axiom is marked by both $f$ and $\ell$.

Sometimes it is easier to assume that the original grammar is in a kind of normal form. In this case Chomsky normal form seems best. Those grammars have only productions of the type $A\to BC$ or $A\to t$. The simplicity of this format means there are much less cases to consider.

  • $\begingroup$ But when we get a production of type $A\to t\alpha$ we don't know if it's the first symbol or the last symbol. So we just say that if $A\to t\alpha$ is the first symbol then $A\to t\alpha$ is $t=a$? $\endgroup$
    – Yos
    Jan 26, 2019 at 12:05
  • 1
    $\begingroup$ When I wrote $A\to t\alpha$ is was to specify that the first symbol in the right-hand-side is the terminal symbol $t$. You are right: only when $t=a$ this can be applied in the first position of the string. $\endgroup$ Jan 26, 2019 at 22:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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