Left Linear Grammer to Right Linear Grammer

1.1k Views Asked by At

I am learning Regular Grammar and given the problem to convert S->S10/0 from left linear to right linear grammar.

I've seen examples of such conversions where we first write the reverse productions of a LLG to RLG and that conversion represents the reverse of the language represented by LLG.

So, then we draw the DFA for the above RLG(reversed language) and reverse the DFA to get the reverse of the reversed language which finally is the the DFA of the RLG that we want to construct. So, then we write the RLG from the drawn DFA.

But, I am not able to implement this process due to 2 terminating symbols present continuously after S (ie- S10 on the right side).

Can someone kindly, provide the correct me how to solve this ?

1

There are 1 best solutions below

0
On

You could first convert the grammar to the form you are used to with only one terminal on the right-hand sides:

$$S \rightarrow A0 | 0 \\ A \rightarrow S1$$

From here you can apply the process you are used to as far as I understand.

On the other hand, the language is so simple that you could just write a right-linear grammar for it, unless you are obliged to apply the process described.