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
View Answer

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

2. Choose the correct option for the given statement:
Statement: The DFA shown represents all strings which has 1 at second last position.
The given figure is NFA with all strings which has 1 at second last position
a) Correct
b) Incorrect, Incomplete DFA
c) Wrong proposition
d) May be correct
View Answer

Answer: c
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
View Answer

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

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)
View Answer

Answer: a
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
View Answer

Answer: c
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.
advertisement

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
View Answer

Answer: c
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:
Find the number of transitions with 1 as its symbol but not 0
a) 4
b) 3
c) 2
d) 1
View Answer

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

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

Answer: b
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
Number of times the state q3 or q2 is being part of extended 6 transition state is 6
a) 6
b) 5
c) 4
d) 7
View Answer

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

10. Predict the missing procedure:
The extended transition state implementation is {Q0, Q2}
i.Δ(Q0, ε) ={Q0},
ii.Δ(Q0, 01) = {Q0, Q1}
iii.δ(Q0, 010) =?
a) {Q0, Q1, Q2}
b) {Q0, Q1}
c) {Q0, Q2}
d) {Q1, Q2}
View Answer

Answer: c
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.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.