Suppose that we expand our idea of context free grammar rules to allow regular expressions of terminals on the right hand side. For example, consider $G_1$:

$\begin{align*} S & \rightarrow (a \mid b) S (c \mid d) \\ S & \rightarrow (a \mid b) A (c \mid d) \\ A & \rightarrow (f \mid g)^* \end{align*} $

Then the language of $G_1$ is the following:
$$L(G_1) = \{(a \mid b)^n (f \mid g)^* (c \mid d)^n \mid n > 0\}$$

Give a standard CFG that has the same language as $G_1$, is your grammar weakly equivalent to $G_1'$, strongly equivalent to $G_1'$, or both? Why?

Secondly, how can I transform any CFG with regular expressions of terminals on the right hand side to a normal context free grammar?

  • 1
    $\begingroup$ These questions have been answered dozens of times in SO. If you're going to post homework, you should at least post your best attempt at a solution. $\endgroup$
    – Apalala
    Feb 7 '13 at 14:39

The general answer is pretty straightforward: if you have a grammar rule of the form $S \rightarrow {\alpha}r{\beta}$, where $r$ is a regular expression over the set of nonterminals, change this production to $S \rightarrow {\alpha}S'{\beta}$, find a right-regular grammar with start symbols $S'$ generating $L(r)$ (there is an algorithm for this); and then your grammar will include all those productions as well. Repeat for every production containing a regular expression on the right-hand side.


A exactly grammar equivalent to G1 is following ( say G2) :

S → X S Y 
S → X A Y 

X → a | b 
Y → c | d

A → fA | gA | ^

Where ^ is a null symbol (epsilon)

exactly equivalent means L(G1) = L(G2) that is language of G1 and G2 are same( every string in L(G1) also in L(G2) and vise-versa).


Your Answer

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