Theory Of Computation : Mid Sem Examination ( 4th Sem )

Theory Of Computation

Mid Semester Examination, 2021-22
B. Tech - Semester : 04
Time : 1.30 hrs. - Max. Marks : 40

Instructions:

1. All questions are Compulsory
2. Assume missing data suitably, if any.

Section : A ( 2 x 2 = 4 Marks )

All questions are compulsory

1. Elaborate various limitations and applications of finite automata.
2. Find regular expression for the strings which accepts all strings beginning or ending with either 01 or 10.

Section : B ( 4 x 2 = 8 Marks )

All questions are compulsory

1. Define nondeterministic finite automata. How does it differ from deterministic finite automata? Explain by giving proper example.
2. Prove that the following Language L = { a^n b^n } is not regular.

Section : C ( 6 x 2 = 12 Marks )

All questions are compulsory

1. For the automata given below, find out whether they are equivalent or not.
   
   
   
   
   -----OR-----
   

   Construct a DFA
   i) Which accepts a string starting and ending with same symbols?
   ii) For regular expressions (a+b)* (aa+bb) (a+b)*
   
   
2. Obtain the equivalent automata without null move.
   
   

   
   
   -----OR-----
   

   Design the regular expression corresponding to the DFA shown below:
   
   

   

   
   

Section : D ( 8 x 2 = 16 Marks )

All questions are compulsory

1. Find the minimum state automata for the given transition diagram.
   
   
   
   
   -----OR-----
   

   Convert the NDFA shown in figure into its equivalent DFA:
   
   

   
   
   
2. Construct a Melay machine
   i) Which can output EVEN, ODD according as the total number of 1's encountered is even or odd? The input symbols are 0 and 1.
   ii) For 2's complement of given string with stepwise description.
   

   -----OR-----
   

   Transition diagram for the Melay machine is given below. Construct the equivalent transition diagram for the Moore machine.
   
   

   

   
   

*******************