Theory of Computation MCQ 3
This page is provided with simple multiple choice questions in Theory of computation.
If the reader want to learn all the concepts of theory of computation. Click Here.
At learning monkey one can learn all the computer science subjects from basics to advanced and GATE for free. Click Here.
1) Which among the following can be an example of application of finite state machine(FSM)?
1) Communication Link
2) Adder
3) Stack
4) None of the mentioned
Answer: 1
2) Which among the following is not an application of FSM?
1) Lexical Analyser
2) BOT
3) State charts
4) None of the mentioned
Answer: 4
3) L1= {w | w does not contain the string tr }
L2= {w | w does contain the string tr}
Given ∑= {t, r}, The difference of the minimum number of states required to form L1 and L2?
1) 0
2) 1
3) 2
4) Cannot be said
Answer: 1
4) Predict the number of transitions required to automate the following language using only 3 states:
L= {w | w ends with 00}
1) 3
2) 2
3) 4
4) Cannot be said
Answer: 1
5) The total number of states to build the given language using DFA:
L= {w | w has exactly 2 a’s and at least 2 b’s}
1) 10
2) 11
3) 12
4) 13
Answer: 1
6) The entity which generate Language is termed as:
a) Automata
b) Tokens
c) Grammar
d) Data
Answer: c
7) Production Rule: aAb->agb belongs to which of the following category?
a) Regular Language
b) Context free Language
c) Context Sensitive Language
d) Recursively Enumerable Language
Answer: c
8) Which of the following statement is false?
a) Context free language is the subset of context sensitive language
b) Regular language is the subset of context sensitive language
c) Recursively enumerable language is the super set of regular language
d) Context sensitive language is a subset of context free language
Answer: d
9) The Grammar can be defined as: G=(V, ∑, p, S)
In the given definition, what does S represents?
a) Accepting State
b) Starting Variable
c) Sensitive Grammar
d) None of these
Answer: b
10) Which among the following cannot be accepted by a regular grammar?
a) L is a set of numbers divisible by 2
b) L is a set of binary complement
c) L is a set of string with odd number of 0
d) L is a set of 0n1n
Answer: d
11) Which of the expression is appropriate?
For production p: a->b where a∈V and b∈_______
a) V
b) S
c) (V+∑)*
d) V+ ∑
Answer: c
12) For S->0S1|e for ∑={0,1}*, which of the following is wrong for the language produced?
a) Non regular language
b) 0n1n | n>=0
c) 0n1n | n>=1
d) None of the mentioned
Answer: d
13) The minimum number of productions required to produce a language consisting of palindrome strings over ∑={a,b} is
a) 3
b) 7
c) 5
d) 6
Answer: c
14) Which of the following statement is correct?
a) All Regular grammar are context free but not vice versa
b) All context free grammar are regular grammar but not vice versa
c) Regular grammar and context free grammar are the same entity
d) None of the mentioned
Answer: a
15) Are ambiguous grammar context free?
a) Yes
b) No
Answer: a
16) Which of the following is not a notion of Context free grammars?
a) Recursive Inference
b) Derivations
c) Sentential forms
d) All of the mentioned
Answer: d
17) State true or false:
Statement: The recursive inference procedure determines that string w is in the language of the variable A, A being the starting variable.
a) true
b) false
Answer: a
18) Which of the following is/are the suitable approaches for inferencing?
a) Recursive Inference
b) Derivations
c) Both Recursive Inference and Derivations
d) None of the mentioned
Answer: c
19) If w belongs to L(G), for some CFG, then w has a parse tree, which defines the syntactic structure of w. w could be:
a) program
b) SQL-query
c) XML document
d) All of the mentioned
Answer: d
20) Is the following statement correct?
Statement: Recursive inference and derivation are equivalent.
a) Yes
b) No
Answer: a