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
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”