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

### View Answer

Answer: a

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

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

a) S * Q -> S

b) Q * Q -> S

c) S * S -> Q

d) Q * S -> Q

### View Answer

Answer:d

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

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

a) 100

b) 1000

c) 1100

d) 0011

### View Answer

Answer: a

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’.

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’.

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

### View Answer

Answer: c

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.

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.

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

### View Answer

Answer: c

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.

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.

((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}

### View Answer

Answer: a

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

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

### View Answer

Answer: d

Explanation: As Kleene operation is not on the whole of the substring, it will not repeat and maintain the order of 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

### View Answer

Answer: b

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

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

a) Transitive Closure properties

b) Brzozowski method

c) State elimination method

d) All of the mentioned

### View Answer

Answer: d

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

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

a) 1(01)* and (10)*1

b) x(xx)* and (xx)*x

c) (ab)* and a*b*

d) x+ and x*x+

### View Answer

Answer : c

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

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

### View Answer

Answer : b

Explanation : None.

Explanation : None.

$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

### View Answer

Answer: c

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’

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’

Statement: A regular expression is a sequence of characters that represent a pattern.

a) true

b) false

### View Answer

Answer: a

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

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

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

### View Answer

Answer: a

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.

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.

a) rule priority

b) longest match rule

c) keyword-out rule

d) none of mentioned

### View Answer

Answer: a

Explanation: The lexical analyzer follows the rule priority where its prioritizes keywords over an input it gets with the same name as that of the keyword and thus generates an error.

Explanation: The lexical analyzer follows the rule priority where its prioritizes keywords over an input it gets with the same name as that of the keyword and thus generates an error.