Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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$?
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.
