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.........

Language to Grammar Conversion

Language to Grammar Conversion:

For understanding language to grammar conversion, let us take an example-

Example 1-  Consider the following language-

                   L(G) = { aⁿ  bⁿ   |  n>=1}

Solution: The above language is the combination of strings of 'a' and 'b' having equal number of 'a' and 'b'.

For making grammar corresponding to above language, first of all we start with starting symbol 'S'.

First production is          S -> aSb   (since number of a's come before number of b's and number of a's equal to number of b's. so we wrote aSb. with this rule, we can increase number of a's and number of b's.

Like   S -> aSb -> aaSbb -> aaaSbbb...........

here we put the value of 'S' again and again and make strings.but with this rule , we can not eliminate Variable 'S'. so we have to write another rule that can eliminate 'S' from strings.

                           S -> ab

this rule makes first string and also eliminate 'S' from the strings produced by first rule.

Final Grammar corresponding to the above language is :

                      { S -> aSb | ab   }

string generated by the above grammar are:

{ab, aabb, aaabbb, aaaabbbb,.............} that is also accepted by the above language.



Example 2:   Consider the following language-

                    L(G) = { aⁿ  b²ⁿ   |  n>=1}


Example 3:   Consider the following language-

                    L(G) = { a²ⁿ  bⁿ   |  n>=1}

Example 4:   Consider the following language-

                    L(G) = { aⁿ  b^m   aⁿ|  n, m >= 1}

Example 5:  Find out the grammar correspond to following language-
          
                L(G) = { aⁱ  b^m   c^m|  m >= 1, i>=0}

solution:  Grammar corresponding to above language are-

                            S -> aS | A
                            A -> bAc | bc

since there is no relation between i and m. so first of all, we have inserted number of a's using S -> aS production rule.
also the above language will generate strings that contains number of  b's and c's only. so we have used S -> A production rule. and for number of b's and c's in equal manner, we have used A -> bAc | bc  production rules.

Example 6:  Find out the grammar correspond to following language-

          

                L(G) = { a^m  b^m   cⁱ|  m >= 1, i>=0}

Example 7:  Find out the grammar correspond to following language-

          

                L(G) = { w c w^T|   w contains strings of 0's and 1's including null}

Solution: Grammar corresponding to above language are

                    S -> aSa | bSb | c 

since the above language also contains null so we have used S -> c production.
also w contains all the string of 0's and 1's and w^T contains all the string of 1's and 0's ( w^T means transpose of w). so we have used productions -
 S -> aSa | bSb. 

Example 8: Let L be the set of all palindrome strings over (0, 1). Construct G generating L.

Solution : Grammar (G) corresponding to above language are-

                  S -> ^
                  S -> 0     S -> 1
                  S -> 0S1    S -> 1S1

since ^ , 0 and 1 are single terminals. and single terminals always a palindrome string. so we have used     S -> ^    S -> 0     S -> 1 production rules.
also for other strings of 0's and 1's, we have used production rules S -> 0S0 and S -> 1S1.

Example 9: Construct a grammar generating {a^m  b^m   c^m  | n>=1 }

Solution:  Grammar (G) corresponding to above language are-

                  S -> aSAc | abc
                  cA -> Ac
                  bA -> bb



other good examples, I will cover later.

Grammar to Language Conversion

Grammar to language Conversion:

Language:  

Language is nothing but the generalization of the number of strings accepted by the grammar.

   For Example-  Consider the following grammar G ( {S}, {a}, P, S):

           where p :    S -> aS | a

                        

Number of string accepted by above grammar are -

{a, aa, aaa, aaaa, aaaaa,.........}

Now the language of the above grammar is 

                    L(G) = { aⁿ     |  n>=1}

where L(G) = language of grammar G.

Details: Strings accepted by above grammar are-

  (since S is the starting symbol, so all the strings will be started from S.) 

First string is -           S -> a
Second String is -       S -> aS ->aa       

Third string is -          S -> aS -> aaS -> aaa        
Fourth string is-         S -> aS -> aaS -> aaaS -> aaaa

and so on....

Grammar to Language Conversion:

There are two methods for grammar to language conversion-

 1)  Simple method

 2)  Tree method

Simple method, that is described above by simple example.

Tree method : 

For understanding the tree method, let us take an example-

Consider the following grammar:

                  S -> aSb | ab

the number of strings accepted by tree method are:

and so on...

The accepted by the above grammar using tree method are ( ab, aabb, aaabbb, aaaabbbb....so on)

Now the generalized form  of the grammar (language) is :

                         L(G) = {aⁿ   bⁿ   | n>=1}


Exercises: 

Find out the language corresponding to following grammar using simple method and tree method:

1.     S -> aSb | aAb
        A -> aAb | c

2.     S -> aSbb | abb
      

Grammar & Types of Grammar

Grammar:

A Grammar is described by four tuples - ( V_N  ,  ∑ ,  P,  S ) 

Where,

            V_N = Finite non empty set of variables

         ∑ =Finite non empty set of terminals (or input alphabets)

         P = Production rules ( X  -> Y where X and Y are the combination of              variable and terminals)

         S = Starting symbol

Note : Variables are represented in capital letters (like A,B,C,D,S,.... etc)

          Terminals are represented by small letters or numbers (like a,b,c..0,1,2...etc)

Classification of Grammar:

This Classification is based on format of production rules-

1) Type 0 grammar: (Grammar with no restriction)

•  It is also called phase structured grammar.
•  This type of grammar is accepted by Turing Machine(TM).

       
2) Type 1 grammar: (Context Sensitive Grammar)

•  it is also called context dependent grammar.
•  Productions are in the form of α  A  β  ->  α B β, where α and  β are  called left context and right context of the grammar respectively.
•  This type of grammar is accepted by Linear bounded automata (LBA).

3) Type 2 grammar: (Context free grammar)

• Productions are in the form A -> α,where α belongs to (V_N  U ∑ )^*

means that left side of the arrow contains only one variable and right side of the arrow contains combination of variables and input terminals including null.

• This type of grammar is accepted by Push down automata (PDA).

4) Type 3 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).

Relation between all grammars: 

type 3 <= type 2 <= type 1 <= type 0

Numericals :

Consider the following grammars-

1.    S -> ABa                   2.   S -> aS | aA         

       A -> aA | a                      A -> aA | a                          

       B -> b                                                             

                                                                             

check whether the above grammar is type 0, type 1 , type 2 or type 3 ?

Solution:

First grammar is Type 2 grammar because in this grammar, the left side of the arrow contains only one variable and right side of the arrow contains the combination of variables and terminals. 

Second grammar is type 3 Grammar because in this grammar, the left side of the arrow contains only one variable and right side of the arrow contains only one terminal or combination of one terminal and one variable.

       

Two - Way Finite Automata

Two - Way Finite Automata

Described by 5 - tuples ( Q , Σ , δ , q₀ , F ), where

• Q is a finite set of states(denoted by capital letters like A, B... etc).
• Σ is a finite set of input terminals (Denoted by small letters like a, b... etc).
• δ is the transition function, that is, δ: Q X Σ → Q X { L, R }
• q₀ is the initial state.
• F is a set of final state

Transition Table : 

States	0	1
-> q0	( q0, R )	( q1, R )
q1 (Final State)	( q1, R )	( q2, L )
q2	( q0, R )	( q2, L )

To understand the concept of  two - way FA and, Let us take an example.

Example : 

Consider the transition table .check the string " 101001 " whether it is accepted by Two - Way DFA or not? 

States	0	1
-> q0	( q0, R )	( q1, R )
q1 (Final State)	( q1, R )	( q2, L )
q2	( q0, R )	( q2, L )

Acceptability of the string using Two - way DFA is -

Here we started from the initial state q0 and finally reached to q1 (final state). so the string "101001" is accepted by Two - Way DFA.

Conversion from Two - Way DFA (2-DFA) to NFA 

• To convert the 2-DFA into NFA, first of all we have to find out the crossing sequence.
• The list of states below each boundary between squares is termed as crossing sequence.
• For making the table of NFA, we have to find out the left match or right match of the states.

Crossing Sequence for the string "101001" of the above example is -

  

Right Match examples of the above crossing sequence-

here {q1} is the right match of {q0} at input "1"

here {q1 q2 q0} is the right match of {q1} at input "0"

Using with the help of above two diagrams for the right match, we make the NFA table. similarly we can make the NFA table using left match.

NFA table is -

States	Right match 0	Right match 1
->[q0]	-	[q1]
[q1] (Final State)	[q1 q2 q0][q1]	-
[q1 q2 q0]	-	[q1]

here there is not any right match of q0 at input"0" but at input "1", right match is q1.

for q1, right match at input "0" is [q1 q2 q0] and [q1] because we check q1 at two places in the crossing sequence diagram and there is not any right match at input "1".

  

Minimization Using Myhill - Neurode Theorem

Minimization using Myhill-Neurode Theorem 

To understand the concept of minimization using Myhill-Neurode Theorem, Let us take an example-

  

To Minimize the above DFA using Myhill-Neurode theorem, follow some steps:

1.> Initially an  X is placed in each entry corresponding to one final state and one non-final state in the following format.

(c,a)  =  X

(c,b)  =  X

(c,d)  =  X

(c,e)  =  X

(c,f)   =  X

(c,g)  =  X

(c,h)  =  X

       

After placing  "X" in the format, then the new format is :

Now take all the blank spaces from the new format like (a,b), (a,d),  (b,d), (a,e), (b,e), (d,e), (a,f), (b,f).....(g,h).

First take (a,b), 

Here for (a,b), we applied input"0" then we got (b,g) and when we applied input"1" then we got (c,f). and Since "X" is already placed correspond to (c,f), so put "X" corresponding to (a,b).

then take (a,d),

Here for (a,d),when we applied input"0" then we got (b,c) and when we applied input"1" then we got (f,g). and Since "X" is already placed correspond to (b,c), so put "X" corresponding to (a,d).

Same process is repeated for , (b,d) and .....(g,h).

then we get the following format:

Here there is no entry corresponding to (a,e) , (b,h) and (d,f). so we combine these states and make a new minimized automata,i,e.,

                

          

Mealy and Moore machine and their conversions

Mealy and Moore machine

Mealy machine : 

• In Mealy machine. the value of output function is depend on the present state and present input.
• Mealy machine is described by 6-tuples - (Q, Σ, Δ, δ, λ, q₀)

          where

          Q = Finite non-empty set of states;

          Σ = Set of input alphabets.

          Δ = Set of output alphabets.

          δ = Transitional function mapping Q X Σ → Q

          λ = Output function mapping Q X Σ → Δ

          q_{0 =} Initial state.

Sample Transition table:

Present State	Next State
	a = 0		a = 1
	State	Output	State	Output
-> q0	q3	0	q1	1
q1	q0	1	q3	0
q2	q2	1	q2	0
q3	q1	0	q0	1

Moore machine : 

• In Moore machine. the value of output function is depend on the present state only.
• Moore machine is described by 6-tuples - (Q, Σ, Δ, δ, λ, q₀)

          where

          Q = Finite non-empty set of states;

          Σ = Set of input alphabets.

          Δ = Set of output alphabets.

          δ = Transition function mapping Q X Σ → Q

          λ = Output function mapping Q → Δ

          q_{0 =} Initial state..

Sample Transition Table:

Present State	Next State		Output
	a = 0	a = 1
-> q0	q3	q1	1
q1	q0	q3	0
q2	q2	q2	0
q3	q1	q0	1

Conversion from Mealy machine to Moore machine:

Steps:

1.>  Determine the number of different output associated with qi in the next state column.

2.> we split qi into different states according to different output associated with it. for ex. suppose in the next state column of the above sample transition table of mealy machine, the output associated with q1 is "0" in the first next state column and "1" in the second next state column. so we split q1 into q10 and q11 states. similarly check others and split them.

Example 1:  consider the above sample transition table of the mealy machine. convert it into corresponding Moore machine.

Solution: After applying the conversion steps, we get two states ( q1 and q2) that are associated with different outputs (0 and 1). so we split both states into q10 , q11 and q20, q21.

Now the transition table becomes

Present State	Next State
	a = 0		a = 1
	State	Output	State	Output
-> q0	q3	0	q11	1
q10	q0	1	q3	0
q11	q0	1	q3	0
q20	q21	1	q20	0
q21	q21	1	q20	0
q3	q10	0	q0	1

Here 

• whole row of q1 is copied to q10 , q11 and whole row of q2 is copied to q20 and q21 of the sample transition table of mealy machine.

• The outputs of the next state columns of q1 and q2 are depend on the previous output. For ex. in the first row, q1 becomes q11 because the out of q1 is 1. in the fourth row, q2 becomes q21 because the output of the q2 is 1. and in the subsequent column q2 becomes q20 because the output of q2 in that column was 0. and so on

now in moore machine format, we copied all the states and common output because in moore machine. the outputs of the next state are common.

Present State	Next State		Output
	a = 0	a = 1
-> q0	q3	q11	1
q10	q0	q3	0
q11	q0	q3	1
q20	q21	q20	0
q21	q21	q20	1
q3	q10	q0	0

This table is moore machine table corresponding to the sample mealy machine.

Exercise : convert the following mealy machine to corresponding moore machine

Present State	Next State
	a = 0		a = 1
	State	Output	State	Output
->q0	q1	0	q3	0
q1	q3	1	q2	0
q2	q4	1	q0	0
q3	q0	0	q4	1
q4	q2	0	q1	1

Conversion from Moore machine to Mealy machine:

For understanding the conversion of moore to mealy machine, let us take an example:

suppose the moore machine transition table is:

Present State	Next State		Output
	a = 0	a = 1
-> q0	q3	q1	1
q1	q0	q3	0
q2	q2	q2	0
q3	q1	q0	1

convert this transition table into mealy machine.

Solution: First of all take the mealy machine transition table format, i.e.,

resent State	Next State
	a = 0		a = 1
	State	Output	State	Output

next step is to copy all the  moore machine transition table states into mealy machine transition table format

Present State	Next State
	a = 0		a = 1
	State	Output	State	Output
-> q0	q3		q1
q1	q0		q3
q2	q2		q2
q3	q1		q0

Now in the moore machine, the output of the q0 is 1. so make the output of q0 in the mealy machine next state column of the above table is 1. same process is repeated for q1, q2 and q3.

Present State	Next State
	a = 0		a = 1
	State	Output	State	Output
-> q0	q3		q1
q1	q0	1	q3
q2	q2		q2
q3	q1		q0	1

After repeating the above process for q1,q2 and q3 states, the final mealy machine transition table is: 

Present State	Next State
	a = 0		a = 1
	State	Output	State	Output
-> q0	q3	1	q1	0
q1	q0	1	q3	1
q2	q2	0	q2	0
q3	q1	0	q0	1

Exercise :  convert the following Moore machine into mealy machine:

Present State	Next State		Output
	a = 0	a = 1
-> q0	q1	q0	0
q1	q2	q3	1
q2	q3	q2	0
q3	q0	q1	1