# Automata Theory Multiple Choice Question & Answers (MCQs) set-18

1. Which of the following options is correct?

Statement 1: Initial State of NFA is Initial State of DFA.

Statement 2: The final state of DFA will be every combination of final state of NFA.

a) Statement 1 is true and Statement 2 is true

b) Statement 1 is true and Statement 2 is false

c) Statement 1 can be true and Statement 2 is true

d) Statement 1 is false and Statement 2 is also false

### View Answer

Explanation: Statement 1 and 2 always true for a given Language.

a) NFA

b) DFA

c) PDA

d) Can’t be said

### View Answer

Explanation: We use the construction method to prove the validity of closure properties of regular languages. Thus, it can be observe, how tedious and complex is the construction of a DFA as compared to an NFA with respect to space.

a) 16

b) 11

c) 5

d) 6

### View Answer

Explanation: If L leads to FA1, then for Lc, the FA can be obtained by exchanging the final and non-final states.

a) Union

b) Negation

c) Kleene Closure

d) None of the mentioned

### View Answer

a) Union

b) Intersection

c) Concatenation

d) Negation

e) Star

f) Kleene closure

5. If L1 is regular L2 is unknown but L1-L2 is regular ,then L2 must be

a) Empty set

b) CFG

c) Decidable

d) Regular

### View Answer

Explanation: Regular is closed under difference.

6. The given NFA represents which of the following NFA

a) (ab U a) *

b) (a*b* U a*)

c) (ab U a*)

d) (ab)* U a*

### View Answer

Explanation: The Regular expression (ab U a) * is converted to NFA in a sequence of stages as it can be clearly seen in the diagram. This NFA consist of 8 stated while its minimized form only contains 2 states.

7. The behaviour of NFA can be simulated using DFA.

a) always

b) never

c) sometimes

d) none of the mentioned

### View Answer

Explanation: For every NFA, there exists an equivalent DFA and vice versa.

8. FL is equivalent to

a) LF

b) F

c) L

d) ?

### View Answer

Explanation : None.

9. L and ~L are recursive enumerable then L is

a) Regular

b) Context free

c) Context sensitive

d) Recursive

### View Answer

Explanation :If L is recursive enumerable and its complement too if and only if L is recursive.

10. Which of the following does not support regular expressions?

a) sed

b) awk

c) emacs

d) none of the mentioned

### View Answer

Explanation: There are many UNIX tools including vi, Emacs, sed, awk and modern programming languages which support regular expressions.

11. Which of the following characters are ignored while lexical analysis?

a) .

b) =

c) #

d) WhiteSpace

### View Answer

Explanation: The lexical analyzer ignores all the whitespaces and fragments the program into tokens.

a) 2

b) 5

c) 3

d) 6

### View Answer

Explanation: We select a string w such that w=xyz and |y|>0 and other conditions. However, there exists an integer n such that |w|>=n for any wÎL.

13. State true or false:

Statement: Pumping lemma gives a necessary but not sufficient condition for a language to be regular.

a) true

b) false

### View Answer

Explanation: The converse of the lemma is not true. There may exists some language which satisfy all the conditions of the lemma and still be non-regular.

a) Softball team

b) Sock picking

c) Hair counting

d) All of the mentioned

### View Answer

Explanation: There are several applications of pigeonhole principle:

Example: The softball team: Suppose 7 people who want to play softball(n=7 items), with a limitation of only 4 softball teams to choose from. The pigeonhole principle tells us that they cannot all play for different teams; there must be atleast one team featuring atleast two of the seven players.

a) regular

b) non regular

c) may be regular

d) none of the mentioned

### View Answer

Explanation: If A and B are regular languages, then A Ç B is a regular language and A n B is equivalent to !(A’ U B’).