MCQ Computer Science

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

1. Given Language: L= {ab U aba}*
If X is the minimum number of states for a DFA and Y is the number of states to construct the NFA,
|X-Y|=?
a) 2
b) 3
c) 4
d) 1

Explanation: Construct the DFA and NFA individually, and the attain the difference of states.

2. Transition function maps.
a) S * Q -> S
b) Q * Q -> S
c) S * S -> Q
d) Q * S -> Q

Explanation: Inputs are state and input string output is states.

3. A binary string is divisible by 4 if and only if it ends with:
a) 100
b) 1000
c) 1100
d) 0011

Explanation: If the string is divisible by four, it surely ends with the substring ‘100’ while a binary string divisible by 2 would surely end with the substring ‘10’.

4. Statement 1: NFA computes the string along parallel paths.
Statement 2: An input can be accepted at more than one place in an NFA.
Which among the following options are most appropriate?
a) Statement 1 is true while 2 is not
b) Statement 1 is false while is not
c) Statement 1 and 2, both are true
d) Statement 1 and 2, both are false

Explanation: While the machine runs on some input string, if it has the choice to split, it goes in all possible way and each one is different copy of the machine. The machine takes subsequent choice to split further giving rise to more copies of the machine getting each copy run parallel. If any one copy of the machine accepts the strings, then NFA accepts, otherwise it rejects.

5. Design a NFA for the language:
L: {an| n is even or divisible by 3}
Which of the following methods can be used to simulate the same.
a) e-NFA
b) Power Construction Method
c) Both (a) and (b)
d) None of the mentioned

Explanation: It is more convenient to simulate a machine using e-NFA else the method of Power Construction is used from the union-closure of DFA’s.

6. Which among the following looks similar to the given expression?
((0+1). (0+1)) *
a) {x? {0,1} *|x is all binary number with even length}
b) {x? {0,1} |x is all binary number with even length}
c) {x? {0,1} *|x is all binary number with odd length}
d) {x? {0,1} |x is all binary number with odd length}

Explanation: The given regular expression corresponds to a language of binary strings which is of even length including a length of 0.

7. Which of the following regular expressions represents the set of strings which do not contain a substring ‘rt’ if ?= {r, t}
a) (rt)*
b) (tr)*
c) (r*t*)
d) (t*r*)

Explanation: As Kleene operation is not on the whole of the substring, it will not repeat and maintain the order of t, r.

8. Concatenation Operation refers to which of the following set operations:
a) Union
b) Dot
c) Kleene
d) Two of the options are correct

Explanation: Two operands are said to be performing Concatenation operation AB = A•B = {xy: x ? A & y ? B}.

9. It is suitable to use ____________ method/methods to convert a DFA to regular expression.
a) Transitive Closure properties
b) Brzozowski method
c) State elimination method
d) All of the mentioned

Explanation: For converting RE to DFA , first we convert RE to NFA (Thompson Construction), and then NFA is converted into DFA(Subset Construction).

10. Which of the following pair of regular expression are not equivalent?
a) 1(01)* and (10)*1
b) x(xx)* and (xx)*x
c) (ab)* and a*b*
d) x+ and x*x+

Explanation : (ab)*=(a*b*)*.

11. Which of the following is true?
a) Every subset of a regular set is regular
b) Every finite subset of non-regular set is regular
c) The union of two non regular set is not regular
d) Infinite union of finite set is regular

Explanation : None.

12. Given segment of code:
\$string1 = “Hello\nWorld\n”;
if (\$string1 =~ m/d\n\z/) {
print “\$string1 is a string “;
print “that ends with ‘d\\n’.\n”;
}
What does the symbol /z does?
a) changes line
b) matches the beginning of a string
c) matches the end of a string
d) none of the mentioned

Explanation: It matches the end of a string and not an internal line.The given segment of code outputs:
Hello
World
is a string that ends with ‘d\n’

13. State true or false:
Statement: A regular expression is a sequence of characters that represent a pattern.
a) true
b) false

Explanation: Such a generated pattern could be a fixed word or describe something like more general.

14. Which of the following options support the given statement?
Statement: A regular expression could be a fixed word or describe something like more general.
a) This flexibility makes Regular expression invaluable.
b) This flexibility makes the Regular expression unvaluable.
c) Both (a) and (b)
d) None of the mentioned

Explanation: Regular expressions are very much invaluable tools; they can be used to find a particular segment of line in a file and instruct to take certain actions.

15. The methodology to show an error when the analyzer faces a keyword over an user’s input is based on:
a) rule priority
b) longest match rule
c) keyword-out rule
d) none of mentioned