Take the 2-minute tour ×
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|improve this question
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
add comment

migrated from stackoverflow.com Feb 8 '13 at 14:13

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

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer


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