Left-Linear and Right-Linear Grammars

Question

I need help with constructing a left-linear and right-linear grammar for the languages below?

a)  (0+1)*00(0+1)*
b)  0*(1(0+1))*
c)  (((01+10)*11)*00)*

For a) I have the following:

Left-linear
S --> B00 | S11
B --> B0|B1|011

Right-linear
S --> 00B | 11S
B --> 0B|1B|0|1

Is this correct? I need help with b & c.

Answer 1

Constructing an equivalent Regular Grammar from a Regular Expression

First, I start with some simple rules to construct Regular Grammar(RG) from Regular Expression(RE).
I am writing rules for Right Linear Grammar (leaving as an exercise to write similar rules for Left Linear Grammar)

NOTE: Capital letters are used for variables, and small for terminals in grammar. NULL symbol is ^. Term 'any number' means zero or more times that is * star closure.

[BASIC IDEA]

• SINGLE TERMINAL: If the RE is simply e (e being any terminal), we can write G, with only one production rule S --> e (where S is the start symbol), is an equivalent RG.

• UNION OPERATION: If the RE is of the form e + f, where both e and f are terminals, we can write G, with two production rules S --> e | f, is an equivalent RG.

• CONCATENATION: If the RE is of the form ef, where both e and f are terminals, we can write G, with two production rules S --> eA, A --> f, is an equivalent RG.

• STAR CLOSURE: If the RE is of the form e*, where e is a terminal and * Kleene star closure operation, we can write two production rules in G, S --> eS | ^, is an equivalent RG.

• PLUS CLOSURE: If the RE is of the form e⁺, where e is a terminal and + Kleene plus closure operation, we can write two production rules in G, S --> eS | e, is an equivalent RG.

• STAR CLOSURE ON UNION: If the RE is of the form (e + f)*, where both e and f are terminals, we can write three production rules in G, S --> eS | fS | ^, is an equivalent RG.

• PLUS CLOSURE ON UNION: If the RE is of the form (e + f)⁺, where both e and f are terminals, we can write four production rules in G, S --> eS | fS | e | f, is an equivalent RG.

• STAR CLOSURE ON CONCATENATION: If the RE is of the form (ef)*, where both e and f are terminals, we can write three production rules in G, S --> eA | ^, A --> fS, is an equivalent RG.

• PLUS CLOSURE ON CONCATENATION: If the RE is of the form (ef)⁺, where both e and f are terminals, we can write three production rules in G, S --> eA, A --> fS | f, is an equivalent RG.

Be sure that you understands all above rules, here is the summary table:

+-------------------------------+--------------------+------------------------+
| TYPE                          | REGULAR-EXPRESSION | RIGHT-LINEAR-GRAMMAR   |
+-------------------------------+--------------------+------------------------+
| SINGLE TERMINAL               | e                  | S --> e                |
| UNION OPERATION               | e + f              | S --> e | f            |
| CONCATENATION                 | ef                 | S --> eA, A --> f      |
| STAR CLOSURE                  | e*                 | S --> eS | ^           |
| PLUS CLOSURE                  | e+                 | S --> eS | e           |
| STAR CLOSURE ON UNION         | (e + f)*           | S --> eS | fS | ^      |
| PLUS CLOSURE ON UNION         | (e + f)+           | S --> eS | fS | e | f  |
| STAR CLOSURE ON CONCATENATION | (ef)*              | S --> eA | ^, A --> fS |
| PLUS CLOSURE ON CONCATENATION | (ef)+              | S --> eA, A --> fS | f |
+-------------------------------+--------------------+------------------------+

note: symbol e and f are terminals, ^ is NULL symbol, and S is the start variable

[ANSWER]

Now, we can come to you problem.

a) (0+1)*00(0+1)*

Language description: All the strings consist of 0s and 1s, containing at-least one pair of 00.

• Right Linear Grammar:

  S --> 0S | 1S | 00A
  A --> 0A | 1A | ^

  String can start with any string of 0s and 1s thats why included rules s --> 0S | 1S and Because at-least one pair of 00 ,there is no null symbol. S --> 00A is included because 0, 1 can be after 00. The symbol A takes care of the 0's and 1's after the 00.

• Left Linear Grammar:

  S --> S0 | S1 | A00
  A --> A0 | A1 | ^

b) 0*(1(0+1))*

Language description: Any number of 0, followed any number of 10 and 11.
{ because 1(0 + 1) = 10 + 11 }

• Right Linear Grammar:

  S --> 0S | A | ^
  A --> 1B
  B --> 0A | 1A | 0 | 1

  String starts with any number of 0 so rule S --> 0S | ^ are included, then rule for generating 10 and 11 for any number of times using A --> 1B and B --> 0A | 1A | 0 | 1.

  Other alternative right linear grammar can be

  S --> 0S | A | ^
  A --> 10A | 11A | 10 | 11

• Left Linear Grammar:

  S --> A | ^
  A --> A10 | A11 | B
  B --> B0 | 0

  An alternative form can be

  S --> S10 | S11 | B | ^
  B --> B0 | 0

c) (((01+10)*11)*00)*

Language description: First is language contains null(^) string because there a * (star) on outside of every thing present inside (). Also if a string in language is not null that defiantly ends with 00. One can simply think this regular expression in the form of ( ( (A)* B )* C )* , where (A)* is (01 + 10)* that is any number of repeat of 01 and 10. If there is a instance of A in string there would be a B defiantly because (A)*B and B is 11.
Some example strings { ^, 00, 0000, 000000, 1100, 111100, 1100111100, 011100, 101100, 01110000, 01101100, 0101011010101100, 101001110001101100 ....}

• Left Linear Grammar:

  S --> A00 | ^
  A --> B11 | S
  B --> B01 | B10 | A

  S --> A00 | ^ because any string is either null, or if it's not null it ends with a 00. When the string ends with 00, the variable A matches the pattern ((01 + 10)* + 11)*. Again this pattern can either be null or must end with 11. If its null, then A matches it with S again i.e the string ends with pattern like (00)*. If the pattern is not null, B matches with (01 + 10)*. When B matches all it can, A starts matching the string again. This closes the out-most * in ((01 + 10)* + 11)*.

• Right Linear Grammar:

  S --> A | 00S | ^
  A --> 01A | 10A | 11S

Second part of you question:

For a) I have the following:
Left-linear
S --> B00 | S11
B --> B0|B1|011

Right-linear
S --> 00B | 11S
B --> 0B|1B|0|1

(answer)
You solution are wrong for following reasons,

Left-linear grammar is wrong Because string 0010 not possible to generate. Right-linear grammar is wrong Because string 1000 is not possible to generate. Although both are in language generated by regular expression of question (a).

EDIT
Adding DFA's for each regular expression. so that one can find it helpful.

a) (0+1)*00(0+1)*

b) 0*(1(0+1))*

c) (((01+10)*11)*00)*

Drawing DFA for this regular expression is trick and complex.
_{For this I wanted to add DFA's}

To simplify the task, we should think the kind formation of RE to me the RE (((01+10)*11)*00)* looks like (a*b)*

(((01+10)*11)* 00 )*
(          a*   b )*

Actually in above expression a it self in the form of (a*b)* that is ((01+10)*11)*

RE (a*b)* is equals to (a + b)*b + ^. The DFA for (ab) is as belows:

DFA for ((01+10)*11)* is:

DFA for (((01+10)*11)* 00 )* is:

_{Try to find similarity in construction of above three DFA. don't move ahead till you don't understand first one}