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

View Answer

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

View Answer

Answer: a
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

View Answer

Answer: c
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) *

View Answer

Answer: a
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

View Answer

Answer: b
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 , *

View Answer

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

View Answer

Answer : b
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

View Answer

Answer: c
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

View Answer

Answer : d
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

View Answer

Answer: b
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

View Answer

Answer: d
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

View Answer

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
c) head to body method
d) All of the mentioned

View Answer

Answer: d
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

View Answer

Answer: d
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

View Answer

Answer: b
Explanation: Pigeon hole principle states the following example: If there exists n=10 pigeons in m=9 holes, then since 10>9, the pigeonhole principle says that at least one hole has more than one pigeon.

Related Articles

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to top button