Q1: If an alphabet has n number of letters, then number of strings of length m will
(A) n + m
(B) n × m
(C) m^n
(D) n^m
Answer: (D) n^m
Q2: Languages generated by Kleene star are always
(A) Finite
(B) Infinite
(C) Sometimes finite & sometimes infinite
(D) None of these
Answer: (B) Infinite
Q3: True or False: [statement context missing]
(A) True
(B) False
(C) Sometimes true & sometimes false
(D) None of these
Answer: (A) True
Q4: ab = (ab)* this expression is
(A) True
(B) False
(C) Can’t be assumed
(D) None of these
Answer: (B) False
Q5: The FA shown can be expressed as
(A) (a + b)*
(B) a* + b*
(C) (ab + ba)*
(D) None of these
Answer: (A) (a + b)*
Q6: If a language is expressed through TG, then that language will have its RE
(A) True
(B) False
(C) Depends on language
(D) None of these
Answer: (A) True
Q7: The given FA accepts language
(A) Finite
(B) Infinite
(C) Depends on alphabet
(D) None of these
Answer: (A) Finite
Q8: In TG there may exist more than one path for a certain string
(A) True
(B) False
(C) Depends on the language
(D) None of these
Answer: (A) True
Q9: In TG there may exist no paths for a certain string
(A) True
(B) False
(C) Depends on the language
(D) None of these
Answer: (A) True
Q10: GTG can have final state
(A) 0
(B) 1
(C) More than 1
(D) All of the given
Answer: (D) All of the given
Q11: The NFA shown, if converted to FA using a transition table, will have number of states
(A) 6
(B) 5
(C) 4
(D) 3
Answer: (C) 4
Q12: The TG accepts the language in which all strings
(A) Ends in b
(B) Begins with b
(C) Ends and begins with b
(D) None of the given
Answer: (A) Ends in b
Q13: The TG has RE
(A) a(a + b)*b + b(a + b)*a
(B) b(b + a)*a + b(a + b)*a
(C) None of these
(D) a(a + b)*a + b(a + b)*b
Answer: (D) a(a + b)*a + b(a + b)*b
Q14: Every FA should be
(A) Deterministic
(B) Non-deterministic
(C) Deterministic & Non-deterministic
(D) None of these
Answer: (A) Deterministic
Q15: One FA has 3 states and 2 letters in the alphabet. Then FA will have number of transitions in the diagram
(A) 4
(B) 5
(C) 7
(D) 6
Answer: (D) 6
Q16: The two TG’s shown are
(A) Equivalent
(B) Non-equivalent
(C) Not valid
(D) None of the given
Answer: (A) Equivalent
Q17: One language can be expressed by more than one NFA
(A) False
(B) True
(C) Depends on NFA
(D) None of the given
Answer: (B) True
Q18: The FA shown generates the strings
(A) Starting and ending with same letters
(B) Starting and ending with different letters
(C) None of these
(D) All of the above
Answer: (A) Starting and ending with same letters
Q19: In FA, if one enters a specific state but there is no way to leave it, then that specific state is called
(A) Dead States
(B) Waste Baskets
(C) Davey John Lockers
(D) All of these
Answer: (A) Dead States
Q20: Using tree structure, final state is represented by
(A) *
(B) –
(C) Double circle
(D) None of given
Answer: (C) Double circle