# Automata Theory Questions and Answers – Extended Transition Function

«
»

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Extended Transition Function”.

1. The number of tuples in an extended Non Deterministic Finite Automaton:
a) 5
b) 6
c) 7
d) 4

Explanation: For NFA or extended transition function on NFA, the tuple elements remains same i.e. 5.

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

Explanation: The given figure is an NFA. The statement contradicts itself.

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

Explanation: q3 does not belong to Q where Q= set of finite states.
Note: Join free Sanfoundry classes at Telegram or Youtube

4. 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) =Upϵs δ(p)
d) δ’ (S) =Up≠s δ(p)

Explanation: According to subset construction, equation 1 holds true.

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

Explanation: DFA is said to be a specific case of NFA and for every NFA that exists for a given language, an equivalent DFA also exists.

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

Explanation: r(n) is the final state and accepts the string S after the string being traversed through r(i) other states where I ϵ 01,2…(n-2).

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

Explanation: The transition graph is made and thus the answer can be found.

8. From the given table, δ*(q0, 011) =? a) {q0}
b) {q1} U {q0, q1, q2}
c) {q2, q1}
d) {q3, q1, q2, q0}

Explanation: δ*(q0,011) = Uδ*(q0,01) δ (r, 1) = {q0, q1, q2}.

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

Explanation: According to the question, presence of q2 or q1 would count so it does and the answer according to the diagram is 6.

10. Predict the missing procedure: i.Δ(Q0, ε) ={Q0},
ii.Δ(Q0, 01) = {Q0, Q1}
iii.δ(Q0, 010) =?
a) {Q0, Q1, Q2}
b) {Q0, Q1}
c) {Q0, Q2}
d) {Q1, Q2}

Explanation: According to given table and extended transition state implementation, we can find the state at which it rests.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers. 