Register Now

Login

Lost Password

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

Login

Register Now

Lorem ipsum dolor sit amet, consectetur adipiscing elit.Morbi adipiscing gravdio, sit amet suscipit risus ultrices eu.Fusce viverra neque at purus laoreet consequa.Vivamus vulputate posuere nisl quis consequat.

CS501 Assignment

Assignment
Question No.1                                                                                                                             Marks: 4
a)      Give regular expressions of the following languages over Σ={0,1}:
1.      All strings having no pair of consecutive zeros. 
2.      All strings having exactly two 1’s or three 1’s not more than it.
b)      Show that the Regular expression ^ + 0(0+1)*+(0+1)*00(0+1)*   is equivalent to  ((0*1)*01*)* 
Solution:
a)       
1.      RE for the language having all strings having no pair of consecutive zeros. 
     
      (1 + 01)*(0 + 1*)
                  Other possibilities might be
                  (1 + 01)*(0 + l) + 1*  or  (1 + 01)* + (1 + 01)*0 + 1*
                  2.   RE for the language having all strings having exactly two 1’s or three 1’s not more than it.
                 
                  0*10*10* + 0*10*10*10*
b)      After generating the string from both regular expressions :
^ + 0(0+1)*+(0+1)*00(0+1)*= ^, 0, 00, 01,001,010,100,011,000,0011,1100………
((0*1)*01*)* = ^,0,00,01,10,010,100,011,101,110,000,……………..
We can see that first RE cannot generate the string ‘10’ while this string can be generated by second RE. So they are not expressing the same language. Hence it is concluded that given Regular expressions are NOT equivalent.

Question No. 2                                                                                                                            Marks: 4
a)      Give recursive definition for the language ODD, of strings defined over ∑={-,0,1,2,3,4,5,6,7,8,9},
b)      Give recursive definition for the language of palindromes having odd length
Solution:
a)       
Step1: 1 is in ODD
Step2: if x is in ODD, then x+2 and x-2 are also in ODD
            Step3: No Strings except those constructed above, are allowed to be in ODD
b)       
            Step1: a and b are in PALINDROME.
Step2: if x is in PALINDROM then axa and bxb are also in PALINDROME
            Step3: No Strings except those constructed above, are allowed to be in PALINDROME
Question No. 3                                                                                                                             Marks: 6
Three Finite Automata (FAs) have been given below:
Match the following Regular Expressions (RE’s) with corresponding Finite Automata (FA’s) given above. Also describe their languages (in English).
Regular Expression
Finite Automaton (FA)
Language Description
a(aa)*(^+a)b+b
aa*b(aa*b)*
(a+b)*a(a+b)*b(a+b)*
Solution:
Regular Expression
Finite Automaton (FA)
Language Description
a(aa)*(^+a)b+b
FA3
All strings in which “b” occurs only one time and that is only at the end of the string.
aa*b(aa*b)*
FA1
All strings which begins with “a” and ends at “b” and not containing the substring “bb”.
(a+b)*a(a+b)*b(a+b)*
FA2
All strings having substring “ab”.
Question No. 4                                                                                                                                 Marks: 6
Build an FA over Σ={a, b} that accepts only those words that do not contain the substring “ba”.
Also make transition table for that FA.
Solution:
FA
Transition table corresponding to above FA
        Old States
New States
After Reading a
After Reading b
q0-
q3
q1
q1+
q2
q1
                    q2
q2
q2
q3+
q3
q1

Leave a reply

About admin

Skip to toolbar