Automata Theory Multiple Choice Quaestion & Answers (MCQs) set-29

1. Number of final state require to accept F in minimal finite automata.
a) 1
b) 2
c) 3
d) None of the mentioned

2. State true or false?
Statement: An NFA can be modified to allow transition without input alphabets, along with one or more transitions on input symbols.
a) True
b) False

3. Which of the following does not belong to input alphabet if S={a, b}* for any language?
a) a
b) b
c) e
d) none of the mentioned

4. Simplify the following regular expression:
e+1*(011) *(1*(011) *) *
a) (1+011) *
b) (1*(011) *)
c) (1+(011) *) *
d) (1011) *

5. Which of the following is not a step in elimination of states procedure?
a) Unifying all the final states into one using e-transitions
b) Unify single transitions to multi transitions that contains union of input
c) Remove states until there is only starting and accepting states
d) Get the resulting regular expression by direct calculation

6. Precedence of regular expression in decreasing order is
a) * , . , +
b) . , * , +
c) . , + , *
d) + , a , *

7. Which of the following is not a regular expression?
a) [(a+b)*-(aa+bb)]*
b) [(0+1)-(0b+a1)*(a+b)]*
c) (01+11+10)*
d) (1+2+0)*(1+2)*
8. What does the following segment of code output?
$string1 = “Hello World\n”;
if ($string1 =~ m/(H..).(l..)/) {
print “We matched ‘$1’ and ‘$2’.\n”;
}
a) We matched ‘Hel’ and ‘ld’
b) We matched ‘Hel’ and ‘lld’
c) We matched ‘Hel’ and ‘lo ‘
d) None of the mentioned
9. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive
10. What does “X?” do regular expression operator?
a) Matches zero or more capital X’s.
b) Matches no or one occurence of the capital letter X.
c) Matches one or more capital X’s.
d) All of the mentioned
11. Lexers and parsers are not found in which of the following?
a) compiler front end processing
b) prettyprinters
c) linters
d) none of the mentioned
12. a ^ nb ^ n where (n+m) is even .
a) Type 0
b) Type 1
c) Type 2
d) Type 3
13. Choose the incorrect process to check whether the string belongs to the language of certain variable or not?
a) recursive inference
b) derivations
c) head to body method
d) All of the mentioned

14. Given languages:
i) {anbn|n>=0}
ii) <div>n</div>n
iii) {w?{a,b}*| #a(w)=#b(w)}, # represents occurrences
Which of the following is/are non regular?
a) i, iii
b) i
c) iii
d) i, ii, iii

15. Which of the following one can relate to the given statement:
Statement: If n items are put into m containers, with n>m, then atleast one container must contain more than one item.
a) Pumping lemma
b) Pigeon Hole principle
c) Count principle
d) None of the mentioned