Finite Automata corresponding to Regular Expression

Finite Automata corresponding to Regular Expression:

For making the finite automata corresponding to regular expression, we have to take the advantage of following automatas - 

1.    R = ^         

2.    R = Ǿ

3.       R = a

4.    R = a*

5.    R = a + b

6.    R = a.b

with the help of these six automatas, we can create finite automata corresponding to regular expression.

Examples in the next post..... enjoy:)




Note: pictures are taken from KLP mishra book scanning.

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