Q.1
All the regular languages can have one or more of the following descriptions:
  • a) i, ii, iv
  • b) i, ii, iii
  • c) i, iv
  • d) i, ii, iii, iv
Q.2
Which of the technique can be used to prove that a language is non regular?
  • a) Ardens theorem
  • b) Pumping Lemma
  • c) Ogden’s Lemma
  • d) None of the mentioned
Q.3
Which of the following language regular?
  • a) {aibi|i>=0}
  • b) {aibi|0<i<5}
  • c) {aibi|i>=1}
  • d) None of the mentioned
Q.4
Which of the following are non regular?
  • a) The set of strings in {a,b}* with an even number of b’s
  • b) The set of strings in {a, b, c}* where there is no c anywhere to the left of a
  • c) The set of strings in {0, 1}* that encode, in binary, an integer w that is a multiple of 3. Interpret the empty strings e as the number 0
  • d) None of the mentioned
Q.5
If L is DFA-regular, L’ is
  • a) Non regular
  • b) DFA-regular
  • c) Non-finite
  • d) None of the mentioned
Q.6
Which of the following options is incorrect?
  • a) A language L is regular if and only if ~L has finite number of equivalent classes
  • b) Let L be a regular language. If ~L has k equivalent classes, then any DFA that recognizes L must have atmost k states
  • c) A language L is NFA-regular if and only if it is DFA-regular
  • d) None of the mentioned
Q.7
Myphill Nerode does the following:
  • a) Minimization of DFA
  • b) Tells us exactly when a language is regular
  • c) Minimization of DFA and tells us exactly when a language is regular
  • d) None of the mentioned
Q.8
Which of the following are related to tree automaton?
  • a) Myphill Nerode Theorem
  • b) State machine
  • c) Courcelle’s Theorem
  • d) All of the mentioned
Q.9
Given languages:
  • a) i, iii
  • b) i
  • c) iii
  • d) i, ii, iii
Q.10
Finite state machine are not able to recognize Palindromes because:
  • a) Finite automata cannot deterministically find the midpoint
  • b) Finite automata cannot remember arbitarily large amount of data
  • c) Even if the mid point is known, it cannot find whether the second half matches the first
  • d) All of the mentioned
0 h : 0 m : 1 s