1. Which of the following are basic complexity classes for a function f:N->N?
a) Ntime(f)
b) Nspace(f)
c) Space(f)
d) All of the mentioned
View Answer
Explanation: Ntime(f): is a set of languages that can be accepted by a NTM T with non deterministic time complexity function t <=f. In all four cases, the machines are allowed to be multitape TM’s.
a) we can reduce the number of tapes
b) we can increase the number of tapes
c) use infinite tapes
d) none of the mentioned
View Answer
3. Which of the following is an application of Finite Automaton?
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned
View Answer
Explanation: There are many applications of finite automata, mainly in the field of Compiler Design and Parsers and Search Engines.
4. Given:
L= {x??= {0,1} |x=0n1n for n>=1}; Can there be a DFA possible for the language?
a) Yes
b) No
View Answer
Explanation: It is not possible to have a count of equal number of 0 and 1 at any instant in DFA. Thus, It is not possible to build a DFA for the given Language.
5. Mealy and Moore machine can be categorized as:
a) Inducers
b) Transducers
c) Turing Machines
d) Linearly Bounder Automata
View Answer
Explanation: They are collectively known as Transducers.
6. Which of the following is a not a part of 5-tuple finite automata?
a) Input alphabet
b) Transition function
c) Initial State
d) Output Alphabet
View Answer
Answer: d
Explanation: A FA can be represented as FA= (Q, ?, d, q0, F) where Q=Finite Set of States, ?=Finite Input Alphabet, d=Transition Function, q0=Initial State, F=Final/Acceptance State).
7. If an Infinite language is passed to Machine M, the subsidiary which gives a finite solution to the infinite input tape is ______________
a) Compiler
b) Interpreter
c) Loader and Linkers
d) None of the mentioned
View Answer
Answer: a
Explanation: A Compiler is used to give a finite solution to an infinite phenomenon. Example of an infinite phenomenon is Language C, etc.
?= {a, b, c}
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: The maximum number of transitions which a DFA allows for a language is the number of elements the transitions constitute.
a) 1
b) 0
c) 2
d) None of the mentioned
View Answer
Explanation: Finite automata doesn’t require any stack operation .
a) Negation
b) Kleene
c) Concatenation
d) None of the mentioned
View Answer
Explanation: NFA is said to be closed under the following operations:
a) Union
b) Intersection
c) Concatenation
d) Kleene
e) Negation
a) Compiler Design
b) Grammar Parsers
c) Text Search
d) All of the mentioned
View Answer
Explanation: There are many applications of finite automata, mainly in the field of Compiler Design and Parsers and Search Engines.
12. e-transitions are
a) conditional
b) unconditional
c) input dependent
d) none of the mentioned
View Answer
Explanation: An epsilon move is a transition from one state to another that doesn’t require any specific condition.
13. State true or false:
Statement: Both NFA and e-NFA recognize exactly the same languages.
a) true
b) false
View Answer
Explanation: e-NFA do come up with a convenient feature but nothing new.They do not extend the class of languages that can be represented.
Language L={x?{0,1}|x is of length 4 or less}
a) (0+1+0+1+0+1+0+1)4
b) (0+1)4
c) (01)4
d) (0+1+e)4
View Answer
Explanation: The extended notation would be (0+1)4 but however, we may allow some or all the factors to be e. Thus e needs to be included in the given regular expression.
a) More than one initial states
b) Null transitions
c) Non-null transitions
d) None of the mentioned
View Answer
Explanation: Arden’s theorem strictly assumes the following;
a) No null transitions in the transition diagrams
b) True for only single initial state
