CS402 Ass Sol

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. {0,1,01,11,10,101,010,011,110…………}

2. {011,110,0110.10101.1101,01101,111,0111,…………….}

b)

Both are equivalent because they generate the same language

                                                                                                                                                      

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 in above are allowed to be in odd

b)

Step 1: 1 is in palindrome

Step2: if x is palindrome, than s(x) Rev(S) and xx is also be palindrome whereas belongs to E*

Step3: no string except one, constructed in above, are allowed to be in Palindrome

Question No. 3                                                                                                                             Marks: 6

Three Finite Automata (FAs) have been given below:

FA1 

 

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	FA 1	Accept  string which start with a and ends with b
aa*b(aa*b)*	FA 3	Accept string which contain only b
(a+b)*a(a+b)*b(a+b)*	FA 2	Accept the string which start with a and ends with b

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.

 

NOTE: - These Assignments OR Quiz are just for idea, so kindly don't copy it, after viewing it make your own. Thanks We always try our best to upload 100% correct solution BUT it is requested that you kindly review it before submission, please BEST OF LUCK, Thanks to those students those send me Assignments and quizzes. If you have any Assignment and quiz kindly send at jamilbookcenter@yahoo.com