Computer science: Theory Of computation MCQs

46. Question

Match all items in Group 1 with correct options from those given in Group 2.
Group 1                                                  Group 2
P. Regular expression                   1. Syntax analysis
Q. Pushdown automata                2. Code generation
R. Dataflow analysis                      3. Lexical analysis
S. Register allocation                   4. Code optimization




Answer
47. Question

Given the following state table of an FSM with two states A and B, one input and one output:

PresentState A PresentState B Input NextState A NextState B Output
0 0 0 0 0 1
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 1 0 0
0 0 1 0 1 0
0 1 1 0 0 1
1 0 1 0 1 1
1 1 1 0 0 1

If the initial state is A = 0, B=0, what is the minimum length of an input string which will take the machine to the state A=0, B=1 with Output=1?




Answer
48. Question

Let  L = L1  ∩ L2 , where L1 and L2 are languages as defined below:

L1={am bm c an bn |m,n >=0}

L2={ai bjck |i,j,k>=0}

Then L is




Answer
49. Question

Untitled

The above DFA accepts the set of all strings over {0,1} that

 




Answer
50. Question

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?




Answer

4 thoughts on “Computer science: Theory Of computation MCQs

  1. Pingback: ugg france pas cher
  2. Pingback: bottes filles chipie

Leave a Reply