Regular Grammar

Regular Grammar

• Productions are in the form of A -> aB   or  A -> a, where A, B are variables and a is terminal. (Left side of the production contains only one variable and right side of the production contains only one terminal or combination of one terminal and one variable (like aB).
• This type of grammar is accepted by Deterministic finite automata (DFA).

Regular Expression:

To represent certain set of strings in an algebraic fashion, we use regular expressions.

Properties: 

1. Any terminal symbol, ^ and  ø are regular expressions.
2. Union of two regular expression (R1 and R2) is also regular expression, means R1 + R2.
3. Concatenation of two regular expression(R1 and R2) is also regular expression, means R1.R2.
4. closure of regular expression(R) is also regular expression, means R^*.
5. If R is a regular expression then (R) is also a regular expression.

Identities for Regular Expression:

There are 12 identities of regular expressions, that are listed below-

1.  ø + R  = R
2.  øR = Rø = R
3.  ^R = R^ = R
4.  ^^{*  = ^  and} Ø^* =ø
5.   R + R = R
6.   R^*R^*  =  R^*
7.   R R^*   =R^*R
8.   (R^*)^* = R^*
9.   ^ +  R R*  = ^ + R^*R  = R^*
10. (QR)^*Q = Q(RQ)^*
11.   (Q + R)^* =  (Q^* R^*)^* = (Q^* + R^*)^*
12. (Q + R) S = QS + RS  and  S (Q + R) = SQ + SR

Theorem: (Arden's Theorem)

let P and Q be two regular expressions over  Σ . if P does not contain ^ , then the following equation in R, 

                       R = Q + RP

has a unique solution given by R = QP* 

Examples:  Describe the following sets by regular expressions:

1. The set of all strings of 0's and 1's ending with 00.

2. The set of all strings of 0's and 1's beginning with 1 and ending with 0.

3. L = { 1, 11, 111, 1111, 11111......}

4. The set of strings over {0,1} which has almost two 1's.

5. The set of strings over {a,b} with three consecutive b's.

Solution:

1.  the set of all strings of 0's and 1's are ( 0 + 1) *

       and these set of strings ending with 00 so place 00 to the end of                                ( 0 + 1) *

   

              So final Set is  -   ( 0 + 1) *00 

2.   Since the set of 0's and 1's are beginning with 1 and ending with 0 so place    1 in the beginning of ( 0 + 1) * and place 0 in the beginning of ( 0 + 1) *.

Now Final Set is  -        1 ( 0 + 1) * 0

3.   Here in the set L, the number of 1's are increasing regularly but this set does not contain null string.

so the final set will be -              [ (1)* - null ]   or  

4. Since this set of string contains at most two a's that mean this set will contain sets having without 1, having single 1 and having two 1's over {0,1}.

set without 1  = 0*

set with single 1 = 0* 1 0*

Set with two 1's  = 0* 1 0* 1 0*

So Final set is  =    [   0*    +   0*10*    +   0*10*10*  ]

5. In this example, we have to place "bbb" between  ( a + b) * and ( a + b) *.

final set is -       [  ( a + b) * bbb ( a + b) * ] 

the above final set will accept all the strings which contains three consecutive b's. you can check with any string of having three consecutive b's.

with the help of these examples, you can solve other examples.........