Converting regular grammar to a regular expression

96 Views Asked by At

I have a regular grammar that looks like:

${S \rightarrow aS, S \rightarrow bB, A\rightarrow \Lambda, A\rightarrow aS, A\rightarrow bB, B\rightarrow aA, B\rightarrow bB, B\rightarrow \Lambda}$

And I need to convert that to a regular expression. The issue I'm having is the problem asks me to eliminate S, then A, then B (in that order). However, I'm not quite sure how to eliminate S first as I end up with a couple productions that don't have any connections (might not be the right word).

For example:

$S^{'} \rightarrow S \space and\space S \rightarrow aS$

gives the production rule of:

$S^{'} \rightarrow a^*$

and

$S^{'} \rightarrow S \space and \space S \rightarrow bB \space$

gives the production rule:

$S^{'} \rightarrow bB$

The first one isn't connected to any other productions like the second one is. Does that mean it is unreachable? Or am I doing it wrong?

1

There are 1 best solutions below

0
On

Figured it out:

$S^{'}\rightarrow S\space and\space S\rightarrow aS \space and \space S\rightarrow bB$

will give the rule:

$S^{'}\rightarrow a^*bB$

I need to make sure all my productions eventually end in a different production letter or else it won't work.