CS402- Theory of Automata Midterm Paper

 MIDTERM  EXAMINATION 

Spring 2009

CS402- Theory of Automata (Session - 1)  

Question No: 1      ( Marks: 1 ) - Please choose one

 Alphabet S = {a,bc,cc} has _______ number of letters.  

        One 

        Two 

        Three 

        Four  

Question No: 2      ( Marks: 1 ) - Please choose one

 In which of the following language Rev(s)=s  

        EQUAL 

        INTEGER 

        PALINDROME 

        FACTORIAL  

Question No: 3      ( Marks: 1 ) - Please choose one

 If S = {ab, bb}, then S* will not contain  

        abbbab 

        bbba 

        bbbbab 

        ababbb  

Question No: 4      ( Marks: 1 ) - Please choose one                                                               

 a,b

      

       1  –

        2 +

 a,b

 Above given FA generates the language having strings of _________  

        ODD length 

        EVEN length 

        Equal number of a’s and b’s 

        None of these  

Question No: 5      ( Marks: 1 ) - Please choose one

 a+b

 a+b

 aa+bb

 -

 +

 Above given GTG accepts the language in which strings   

        Contains double a or double b 

        Contains both a and double b 

        Depends on the alphabet 

        None of these  

Question No: 6      ( Marks: 1 ) - Please choose one

 aa+bb

 aa+bb

 ab+ba

 3-  2  1

     

             

 ab+ba

 4+

      

 If above given TG is drawn like                            

 aa+bb

             

3  1

 X 

-

     

 4

+

Then what will be written in place of X.  

        (ab+ba)(aa+bb)(ba+ab) 

        (ab+ba)(aa+bb)(ab+ba) 

        (ab+ba)(aa+bb)*(ab+ba) 

        (ab+ba)(aa+bb)(ab+ba)*  

Question No: 7      ( Marks: 1 ) - Please choose one

 FA3 expresses r1r2. Then initial state of FA3 will consist of  

        Initial state of FA2 

        Initial state of FA1 

        Initial states of both FA1 & FA2 

        Depends on FA’s  

Question No: 8      ( Marks: 1 ) - Please choose one

 FA3 expresses r1r2. Then there will be at least one final state of FA3 that consist

of final state of FA1 and initial state of FA2.  

        True 

        False 

        Depends on language 

        None of these                                           

Question No: 9      ( Marks: 1 ) - Please choose one

 Two machines are said to be equivalent if they print the same output string when

the different input string is run on them  

        True 

        False 

        Depends on language 

        May be or may not be  

Question No: 10      ( Marks: 1 ) - Please choose one

 Running the string abbabbba on this Moore machine. The outputs will

be________

 b

              q1/0  q2 /1

 a  b

 a

      q0/1   a

b

 a

q3/1  1

 b

 b

 a

2

 q3 /0

        101111010 

        01111010  

        01011110 

        01010101  

Question No: 11      ( Marks: 1 ) - Please choose one                                                                   

 4  a

 2

 a

 a

 a, b a, b

·         1 –    6+

§         a,b

§         a,b

o        b

o        b

 aaa,bbb

 b

 -

5

 3  +

 Above given TG’s are ______________.  

        None of these 

        Equivalent 

        Non-equivalent 

        TG’s are not valid  

Question No: 12      ( Marks: 1 ) - Please choose one

 TG can have more than one initial state.  

        True 

        False 

        Depends on alphabets 

        None of these  

Question No: 13      ( Marks: 1 ) - Please choose one

 a

 a

    

     

 +

 – –   

 a

 b

 b

   

 b

Above given FA accepts null string.

        True 

        False 

        FA is not valid 

        None of these 

Question No: 14      ( Marks: 1 ) - Please choose one

 If in an NFA,   is allowed to be a label of an edge then that NFA is called   _________.  

        Will not remain NFA 

        NFA with 

         NFA with null string 

        Either "NFA with null string" OR "NFA with   "  

Question No: 15      ( Marks: 1 ) - Please choose one

 One FA has n states and m letters in the alphabet. Then FA will have _____

number of transitions in the diagram. 

        (n)+(m) 

        (m)(n) OR (n)(m) 

        None of the given options 

        (m)-(n) 

Question No: 16      ( Marks: 1 ) - Please choose one

 (a+b)*a(a+b)*b(a+b)* is the RE of  language defined over S={a,b} having at least one a

and one b 

        True 

        False 

        Such a language does not exist 

        None of the given options 

Question No: 17      ( Marks: 1 )

 Is the following statement trure?

A regular language can not be infinite.  

Question No: 18      ( Marks: 1 )

 Can you say that for a certain string there may be more than one paths in a TG? 

Question No: 19      ( Marks: 2 )

 If a language can be accepted by an FA then it can be accepted by a TG as well.

What are the other two statements of kleenes’s theorem?  

Question No: 20      ( Marks: 3 )

 Describe the method of NFA corresponding to Concatenation of FAs.  

Question No: 21      ( Marks: 5 )

 Draw FA corresponding to following NFA? 

 2

 b

 a

             1-  4+

a

b

 3

    

Question No: 22      ( Marks: 10 )

 Let L be any language. Let us define the transpose of L to be the language of exactly

those words that are the words in L spelled backward. If w   L then reverse (w)   L. for

example, if L = {a, abb, bbaab, bbbaa}Then Transpose (L) = {a, bba, baabb, aabbb,

Prove that if there is an FA that accepts L, then there is a TG that accepts the transpose of

L.