CFG with regular expression terminals on RHS

Question

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?

Answer 1

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.

Answer 2

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