Explore topic-wise MCQs in Automata Theory.

This section includes 13 Mcqs, each offering curated multiple-choice questions to sharpen your Automata Theory knowledge and support exam preparation. Choose a topic below to get started.

1.

Predict the missing procedure: 1.Δ(Q0, ε) ={Q0},2.Δ(Q0, 01) = {Q0, Q1}3.δ(Q0, 010) =?

A. {Q0, Q1, Q2}
B. {Q0, Q1}
C. {Q0, Q2}
D. {Q1, Q2}View Answer
Answer» D. {Q1, Q2}View Answer
Discussion
2.

Number of times the state q3 or q2 is being a part of extended 6 transition state is

A. 6
B. 5
C. 4
D. 7
Answer» B. 5
Discussion
3.

From the given table, δ*(q0, 011) =?

A. {q0}
B. {q1} U {q0, q1, q2}
C. {q2, q1}
D. {q3, q1, q2, q0}
Answer» C. {q2, q1}
Discussion
4.

According to the given table, compute the number of transitions with 1 as its symbol but not 0:

A. 4
B. 3
C. 2
D. 1
Answer» E.
Discussion
5.

If a string S is accepted by a finite state automaton, S=s1s2s3……sn where siϵ∑ and there exists a sequence of states r0, r1, r2…… rn such that δ(r(i), si+1) =ri+1 for each 0, 1, …n-1, then r(n) is:

A. initial state
B. transition symbol
C. accepting state
D. intermediate state
Answer» D. intermediate state
Discussion
6.

If δ is the transition function for a given NFA, then we define the δ’ for the DFA accepting the same language would be:Note: S is a subset of Q and a is a symbol.a) δ’ (S, a) =Upϵs δ (p, a)b) δ’ (S, a) =Up≠s δ (p, a)c) δ’ (S,

A. δ’ (S, a) =Upϵs δ (p, a)
B. δ’ (S, a) =Up≠s δ (p, a)
C. δ’ (S, a) =Upϵs δ(p)
D. δ’ (S) =Up≠s δ(p)
Answer» B. δ’ (S, a) =Up≠s δ (p, a)
Discussion
7.

What is wrong in the given definition?Def: ({q0, q1, q2}, {0,1}, δ, q3, {q3})

A. The definition does not satisfy 5 Tuple definition of NFA
B. There are no transition definition
C. Initial and Final states do not belong to the Graph
D. Initial and final states can’t be same
Answer» D. Initial and final states can’t be same
Discussion
8.

Choose the correct option for the given statement:Statement: The DFA shown represents all strings which has 1 at second last position.

A. Correct
B. Incorrect, Incomplete DFA
C. Wrong proposition
D. May be correct
Answer» D. May be correct
Discussion
9.

If a string S is accepted by a finite state automaton, S=s1s2s3……sn where siϵ∑ and there exists a sequence of states r0, r1, r2…… rn such that δ(r(i), si+1) =ri+1 for each 0, 1, …n-1, then r(n) is:$

A. initial state
B. transition symbol
C. accepting state
D. intermediate state
Answer» D. intermediate state
Discussion
10.

What is the relation between DFA and NFA on the basis of computational power?

A. DFA > NFA
B. NFA > DFA
C. Equal
D. Can’t be said
Answer» D. Can‚Äö√Ñ√∂‚àö√ë‚àö¬•t be said
Discussion
11.

If δ is the transition function for a given NFA, then we define the δ’ for the DFA accepting the same language would be:$

A.
B. δ’ (S, a) =U<sub>pϵs</sub> δ (p, a)
C. δ’ (S, a) =U<sub>p≠s</sub> δ (p, a)
Answer» B. ‚âà√≠¬¨‚Ä¢‚Äö√Ñ√∂‚àö√ë‚àö¬• (S, a) =U<sub>p‚âà√¨¬¨¬µs</sub> ‚âà√≠¬¨‚Ä¢ (p, a)
Discussion
12.

What is wrong in the given definition?

A.
B. The definition does not satisfy 5 Tuple definition of NFA
C. There are no transition definition
D. Initial and Final states do not belong to the Graph
Answer» D. Initial and Final states do not belong to the Graph
Discussion
13.

The number of tuples in an extended Non Deterministic Finite Automaton:

A. 5
B. 6
C. 7
D. 4
Answer» B. 6
Discussion