Automata Theory Questions and Answers – Programming Techniques-Storage and Subroutines

This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “Programming Techniques-Storage and Subroutines”.

1. A turing machine has ____________ number of states in a CPU.
a) finite
b) infinte
c) May be finite
d) None of the mentioned
View Answer

Answer: a
Explanation: A turing machine has finite number of states in its CPU. However, the states are not small in number. Real computer consist of registers which can store values (fixed number of bits).

2. Suppose we have a simple computer with control unit holding a PC with a 32 bit address + Arithmetic unit holding one double length 64 bit Arithmetic Register. The number of states the finite machine will hold:
a) 2(32*64)
b) 296
c) 96
d) 32
View Answer

Answer: b
Explanation: According to the statistics of the question, we will have a finite machine with 2^96 states.

3. In one move a turing machine will:
Find the move of a turing machine in finite control
a) Change a state
b) Write a tape symbol in the cell scanned
c) Move the tape head left or right
d) All of the mentioned
View Answer

Answer: d
Explanation: A move of a turing machine is the function of the state of finite control and the tape symbol just scanned.
advertisement
advertisement

4. State true or false:
Statement: We can use the finite control of turing machine to hold a finite amount of data.
a) true
b) false
View Answer

Answer: a
Explanation:
The following technique requires no extension to the Turing Machine model
The finite control not only contains state q but also three data, A, B, C. The following technique requires no extension to the Turing Machine model. Shaping states this way allows to describe transitions in more systematic way and often to simplify the strategy of the program.

5. Statement 1: Multitrack Turing machine.
Statement 2: Gamma is Cartesian product of a finite number of finite sets.
Which among the following is the correct option?
a) Statement 1 is the assertion and Statement 2 is the reason
b) Statement 1 is the reason and Statement 2 is the assertion
c) Statement 1 and Statement 2 are independent from each other
d) None of the mentioned
View Answer

Answer: a
Explanation: Cartesian product works like a struct in C/C++. For Example: Computer tape storage is something like 8 or 9 bits in each cell. One can recognize a multi track tape machine by looking at the transitions because each will have tuples as the read and write symbols.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

6. A multi track turing machine can described as a 6-tuple (Q, X, S, d, q0, F) where X represents:
a) input alphabet
b) tape alphabet
c) shift symbols
d) none of the mentioned
View Answer

Answer: b
Explanation: The 6-tuple (Q, X, S, d, q0, F) can be explained as:
Q represents finite set of states,
X represents the tape alphabet,
S represents the input alphabet
d represents the relation on states and the symbols
q0 represents the initial state
F represents the set of final states.

7. Which of the following statements are false?
a) A multi track turing machine is a special kind of multi tape turing machine
b) 4-heads move independently along 4-tracks in standard 4-tape turing machine
c) In a n-track turing machine, n head reads and writes on all the tracks simultaneously.
d) All of the mentioned
View Answer

Answer: c
Explanation: In a n-track turing machine, one head reads and writes on all the tracks simultaneously.
advertisement

8. State true or false:
Statement: Two track turing machine is equivalent to a standard turing machine.
a) true
b) false
View Answer

Answer: a
Explanation: This can be generalized for n- tracks and can be proved equivalent using ennumerable languages.

9. Which of the following is/are not true for recursively enumerable language?
a) partially decidable
b) Turing acceptable
c) Turing Recognizable
d) None of the mentioned
View Answer

Answer: d
Explanation: In automata theory, a formal language is called recursively enumerable language or partially decidable or semi decidable or turing acceptable or turing recognizable if there exists a turing machine which will enumerate all valid strings of the language.
advertisement

10. According to Chomsky hierarchy, which of the following is adopted by Recursively Ennumerable language?
a) Type 0
b) Type 1
c) Type 2
d) Type 3
View Answer

Answer: a
Explanation: Recursively Ennumerable languages are type 0 languages in the Chomsky hierarchy. All regular, context free, context sensitive languages are recursively enumerable language.

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.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

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 & discussions at Telegram SanfoundryClasses.