Question

How to change regular expression to regular grammar? Please give me with details and explain me with easy ways. For instance (10*)*(110v001)* Binary strings contain substring 1001 Binary bring contains exactly two zeros

Answer 1

a) (10*)*(110v001)*

The production rule to generate a* is given as:

A -> aA | lamda

Hence, the production rule fo 10* is given as:

S1 -> 1A

A -> 0A | lamda

Similarly, the production rule for (10*)* is:

S2 -> 1AS1 | lamda

S1 -> 1A | lamda

A -> 0A | lamda

Now, the production rule for (110 v 001)* is given as:

S3 -> 110S3 | 110S3 | lamda

Hence, the overall grammar is:

S -> 1AS1S3 | lamda

S1 -> 1A | lamda

A -> 0A | lamda

S3 -> 110S3 | 110S3 | lamda

2)

Similarly the regular grammar for Binary strings contain substring 1001 is given as:

S -> 0A1001A | 1A1001A | 1001

A -> 0A | 1A | lamda

3)

The regular grammar for Binary strings contains exactly two zeros is:

S -> 1A0A0A | 00

A -> 1A | lamda