# Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

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

Ans- d. All of the mentioned

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

a. always

b. never

c. sometimes

d. none of the mentioned

Ans- a. always

3. Which of the following methods is suitable for conversion of DFA to RE?

a. Brzozowski method

b. Arden's method

c. Walter's method

d. All of the mentioned

Ans- a. Brzozowski method

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

Ans- b. Unify single transitions to multi transitions that contains union of input

5. If we have more than one accepting states or an accepting state with an outdegree, which of the following actions will be taken?

b. removal of a state

c. make the newly added state as final

d. more than one option is correct

Ans- d. more than one option is correct

6. Which of the following is an utility of state elimination phenomenon?

a. DFA to NFA

b. NFA to DFA

c. DFA to Regular Expression

d. All of the mentioned

Ans- c. DFA to Regular Expression

7. The minimum number of transitions to pass to reach the final state as per the following regular expression is: {a,b}*{baaa}

a. 4

b. 5

c. 6

d. 3

Ans- a. 4

8. The total number of states required to automate the given regular expression : (00)(11)

a. 3

b. 4

c. 5

d. 6

Ans- c. 5

9. Which of the following statements is not true?

a. Every language defined by any of the automata is also defined by a regular expression

b. Every language defined by a regular expression can be represented using a DFA

c. Every language defined by a regular expression can be represented using NFA with e moves

d. Regular expression is just another representation for any automata definition

Ans- b. Every language defined by a regular expression can be represented using a DFA

10. Which among the following is equivalent to the given regular expression? : 01*+1

a. (01)*+1

b. 0((1)*+1)

c. (0(1)*)+1

d. ((0*1)1*)*

Ans- c. (0(1)*)+1