MCQ Computer Science

# 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

Explanation: No final state requires.

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

Explanation: It is possible to construct an NFA with e-transitions, presence of no input symbols, and that is called NFA with e-moves.

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

Explanation: The automaton may be allowed to change its state without reading the input symbol using epsilon but this does not mean that epsilon has become an input symbol. On the contrary, one assumes that the symbol epsilon does not belong to any alphabet.

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

Explanation: e+1*(011) *(1*(011) *) *
e + RR*= e + R*R= e + R+= R*

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

Explanation: While eliminating the states, we unify multiple transitions to one transition that contains union of input and not the vice versa.

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

Explanation : None.

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)*

Explanation : Except b all are regular expression*.

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

Explanation: () groups a series of pattern element to a single element.
When we use pattern in parenthesis, we can use any of ‘\$1’, ‘\$2’ later to refer to the previously matched pattern.

9. L and ~L are recursive enumerable then L is
a) Regular
b) Context free
c) Context sensitive
d) Recursive

Explanation :If L is recursive enumerable and its complement too if and only if L is 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

Explanation: There are many other common regular expression operators like \$, ^, etc. Which have their own respective purposes.

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

Explanation: Lexers and parsers are most commonly used in compilers, but it has more application elsewhere like in prettyprinters or linters(application of stylistic formatting conventions to textfiles, source code, etc.).

12. a ^ nb ^ n where (n+m) is even .
a) Type 0
b) Type 1
c) Type 2
d) Type 3

Explanation: It is a regular expression.

13. Choose the incorrect process to check whether the string belongs to the language of certain variable or not?
a) recursive inference
b) derivations
d) All of the mentioned

Explanation: There are two approaches to infer that certain string are in the language of a certain variable. The most conventional way is to use the rules from body to head, recursive inference. The second approach is expanding the starting variable using one of its productions whose head is tart symbol and derive a string consisting entirely of terminals(head to body or derivations).

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

Explanation: There is no regular expression that can parse HTML documents. Other options are also non-regular as they cannot be drawn into finite automaton.

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