Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|cite|improve this question

migrated from Feb 8 '13 at 14:13

This question came from our site for professional and enthusiast programmers.

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. – Apalala Feb 7 '13 at 14:39

2 Answers 2

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.

share|cite|improve this answer

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).

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.