Theory of Computation MCQ (Multiple Choice Questions) - SchoolingAxis

Theory of Computation MCQ (Multiple Choice Questions)

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?

a. addition of new state

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

 

Previous Post Next Post

Responsive Ad