1. If every aRb implies bRa then a relation R will be a symmetric relation.
a) True
b) False
Explanation: a is related to b by R, and if b is also related to a by the same relation R.
2. If every aRb and bRc implies aRc, then the relation is transitive.
a) True
b) False
Explanation: a is related to b by R, and b is related to c by R, and similarly for a and c.
3. The smallest set A such that A ∪ {1, 2} = {1, 2, 3, 5, 9} is?
a) {2,3,5}
b) {1, 2, 5, 9}
c) {3, 5, 9}
d) None of the mentioned
Explanation: Given A ∪ {1, 2} = {1, 2, 3, 5, 9}. Hence A = {3,5,9}.
4. If a set A has n elements, then the total number of subsets of A is?
a) N
b) 2n
c) N2
d) 2n
Explanation: Number of subsets of A = nC0 + nC1 + . . . . . + nCn = 2n.
5. A language L from a grammar G = { VN, Σ, P, S} is?
a) Set of symbols over VN
b) Set of symbols over Σ
c) Set of symbols over P
d) Set of symbols over S
Explanation: The definition of the grammar is set of symbols over Σ.
6. What is the transitional function of a DFA?
a) Q X Σ→Q
b) Q X Σ→2Q
c) Q X Σ→2n
d) Q X Σ→Qn
Explanation: Q is the finite set and let be a finite set of symbols so Q X Σ fives no of states.
7. What is the transitional function of an NFA?
a) Q X Σ→Q
b) Q X Σ→2Q
c) Q X Σ→2n
d) Q X Σ→Qn
Explanation: Let Q be a finite set and let be a finite set of symbols. Also let be a function from Q to 2Q. All the elements of Q a state, the transition function, q0 the initial state and A the set of accepting states.
Then a nondeterministic finite automaton is a 5-tuple < Q, , q0, , A >.
8. Maximum number of states of a DFA converted from an NFA with nstates is?
a) n
b) n2
c) 2n
d) None of the mentioned
Explanation: Take the NFA with states {qo,q1}, alphabet Σ={a}, initial state q0, transitions δ(q0,a)=q0, δ(q0,a)=q1 and final state q1. It generates the same language as the DFA with the same set of states and alphabet, but transitions δ(q0,a)=q1 and δ(q1,a)=q1.
9. What are the basic limitations of finite state machine?
a) It cannot remember arbitrarily large amount of information
b) In cannot remember state transitions
c) In cannot remember grammar for a language
d) It cannot remember language generated from a grammar
Explanation: Because it does to store its previous state of the transition.
10. The string WWR is not recognized by any FSM because _____________
a) An FSM cannot remember arbitrarily large amount of information
b) An FSM cannot fix the midpoint
c) An FSM cannot match W with WR
d) An FSM cannot remember first and last inputs
Explanation: Palindromes cannot be recognized by FSM.