Question 1

The set which is not countable if we have ? = {a, b}, is
A)Set of all languages over ? accepted by turing machine
B)Set of all regular languages over ?
C)Set of all strings over ?
D)Set of all languages over ?

Accepted Answer

D

Question 2

How many states are present in the minimum state finite automaton that recognizes the language represented by the regular expression (0+1)(0+1)…..N times?
A)n+1
B)n+2
C)n
D)2n

Accepted Answer

B

Question 3

Consider the state table of a finite state machine that has input x and a single output z. The shortest input sequence to reach the final state C if the initial state is unknown is
A)10
B)01
C)101
D)110

Accepted Answer

A

Question 4

The set that can be recognized by a deterministic finite state automaton is
A)The set {1, 101, 11011, 1110111, …….}
B)The set of binary string in which the number of 0's is same as the number of1's
C)1, 2, 4, 8……2n ….. written in binary
D)1, 2, 4, 8……2n ….. written in unary

Accepted Answer

A deterministic finite state automaton can recognize regular languages. The set of numbers like 1, 2, 4, 8, ..., 2^n written in binary can be recognized by a DFA because it can be described by a regular expression or a regular grammar.

Question 5

What is the reason behind a Turing machine is more powerful than finite state machine FSM?
A)turing machine head movement is continued to one direction.
B)turing machine head moment is in both directions i.e. left moment and right moment as well.
C)turing machine has capability remember arbitrary long sequence of input string.
D)all are correct.

Accepted Answer

A Turing machine can remember an arbitrary long sequence of input because it has an infinite tape, unlike a finite state machine which has limited memory.

Question 6

A pushdown automata behaves like a Turing machine, when it has number of auxiliary/ memory.
A)0
B)exectly 2
C)2 or more
D)both exectly 2 or more are correct

Accepted Answer

A pushdown automata behaves like a Turing machine when it has 2 or more stacks, as it can simulate the behavior of a Turing machine with multiple stacks.

Question 7

The language L = {anbnan n? 1} is recognized by
A)turing machine
B)2 pushdown automata
C)post machine
D)all are correct

Accepted Answer

The language L = {anbnan | n ≥ 1} is context-sensitive and can be recognized by all the given options: a Turing machine, 2 pushdown automata (using one to handle each half of the pattern), and a Post machine, as all are capable of recognizing context-sensitive languages.

Question 8

If Turing machine accepts all the words of the languages L and rejects or loops for other words, which are not in L, then L is said to be
A)recursive enumerable
B)recursive
C)context free language (cfl)
D)none of them

Accepted Answer

A Turing machine that accepts all words of a language L and either rejects or loops for words not in L defines L as recursively enumerable. This means L can be listed or enumerated by a Turing machine, but not necessarily decided (where every input must lead to acceptance or rejection).

Question 9

If a Turing machine halts for each and every world of a language L and rejects other, then L is said to be
A)recursive enumerable
B)recursive
C)context free language
D)none of these

Accepted Answer

The answer of If a Turing machine halts for each...

Question 10

Universal Turing machine (UTM) influenced the concepts of
A)computability
B)interpretive implementation of programming language
C)program and data is in same memory
D)all are correct

Accepted Answer

The Universal Turing Machine (UTM) is foundational to the concept of computability, it influenced the development of interpretive implementations of programming languages, and it embodies the principle of storing both program and data in the same memory.

Question 11

The number of symbols necessary to simulate a Turing machine with m symbols and n states
A)4m × n + m
B)4m × n + n
C)m+n
D)none of them

Accepted Answer

The number of symbols necessary to simulate a Turing machine with m symbols and n states is 4m × n + m. This is because the Turing machine needs to be able to represent the current state, the current symbol, the next state, and the next symbol. The current state and the next state can be represented with n symbols each, and the current symbol and the next symbol can be represented with m symbols each. Therefore, the total number of symbols needed is 4m × n + m.

Question 12

A universal Turing machine is a
A)reprogrammable truing machine
B)two-tape turing machine
C)single tape turing machine
D)none of them

Accepted Answer

A universal Turing machine is essentially a reprogrammable Turing machine, designed to simulate any other Turing machine. It can read a description of another Turing machine and execute it, thus demonstrating the concept of programmability and universality in computation.

Question 13

He difference between a read-only Turing machine and a two-way finite state machine is
A)head movement
B)finite control
C)storage capacity
D)power

Accepted Answer

A read-only Turing machine has infinite tape for storage, whereas a two-way finite state machine has no additional storage beyond its finite control.

Question 14

Which is correct regard an off-line Truing machine?
A)an offline turing machine is a special type of multi-tape turing machine
B)an offline turing machine is a kind of multi-tracks truing machine
C)an offline turing machine is a kind of single-track turing machine
D)none of them

Accepted Answer

An offline Turing machine is a special type of multi-tape Turing machine where one of the tapes is read-only and contains the input, while the other tapes are used for computation.

Question 15

Which of the following statement is wrong?
A)power of ntm and tm is same
B)for n ? 2, npda has some power as a tm
C)for n ? 2, npda and 2pda have same power
D)power of ntm and tm is not same

Accepted Answer

Power of NTM and TM is same.

Question 16

Four pairs are following; in each pair both objects have some common thing. Choose the odd pair;
A)(tm, 2pda)
B)(computer, utm)
C)(2pda, npda)
D)(fa, pda)

Accepted Answer

The answer of Four pairs are following; in each pair...

Question 17

We think of a Turing machine's transition function as a
A)computer system
B)software
C)hardware
D)all of them

Accepted Answer

The answer of We think of a Turing machine's transition...

Question 18

Church's Thesis supports
A)a turing machine as a general-purpose computer system
B)a turing machine an algorithm and an algorithm as a turing machine
C)both tm is an general-purpose computer and tm is an algorithm and vice-versa are correct
D)none of them is correct

Accepted Answer

Church's Thesis, also known as the Church-Turing thesis, posits that any function that can be computed by an algorithm can be computed by a Turing machine, and vice versa. This effectively supports the idea of a Turing machine as a general-purpose computer system (A) and equates the concepts of a Turing machine and an algorithm (B), making both A and B correct, hence C is the correct choice.

Question 19

A random access machine (RAM) and truing machine are different in
A)power
B)accessing
C)storage
D)both accessing and storage are correct

Accepted Answer

RAM models have direct access to their storage, allowing them to retrieve any piece of data in constant time, whereas Turing machines work with sequential access, reading and writing data in a linear fashion. This difference affects both how they access data and the nature of their storage mechanisms.

Question 20

Choose the correct statement
A)recursive set ? recursive enumerable set
B)total function is same as partial function
C)recursive sets are analogous to total functions
D)both recursive set ? recursive enumerable set and recursive sets are analogous to total functions are correct.

Accepted Answer

Recursive sets, also known as decidable or computable sets, are indeed analogous to total functions, where every input has a defined output. Recursive enumerable sets, on the other hand, are semi-decidable or computably enumerable, meaning that if an element is in the set, there is a procedure to confirm its membership, but if it's not, the procedure may never halt. This distinction aligns with the difference between total functions (defined for every input) and partial functions (not necessarily defined for every input). Thus, both statements in D are correct, reflecting the relationship between these computational concepts.

Quiz 5: Automata and Turing Machines

The set which is not countable if we have ? = {a, b}, is

How many states are present in the minimum state finite automaton that recognizes the language represented by the regular expression (0+1) (0+1) …..N times?

Consider the state table of a finite state machine that has input x and a single output z. The shortest input sequence to reach the final state C if the initial state is unknown is

The set that can be recognized by a deterministic finite state automaton is

What is the reason behind a Turing machine is more powerful than finite state machine FSM?

A pushdown automata behaves like a Turing machine, when it has number of auxiliary/ memory.

The language L = {anbnan n? 1} is recognized by

If Turing machine accepts all the words of the languages L and rejects or loops for other words, which are not in L, then L is said to be

If a Turing machine halts for each and every world of a language L and rejects other, then L is said to be

Universal Turing machine (UTM) influenced the concepts of

The number of symbols necessary to simulate a Turing machine with m symbols and n states

A universal Turing machine is a

He difference between a read-only Turing machine and a two-way finite state machine is

Which is correct regard an off-line Truing machine?

Which of the following statement is wrong?

Four pairs are following; in each pair both objects have some common thing. Choose the odd pair;

We think of a Turing machine's transition function as a

Church's Thesis supports

A random access machine (RAM) and truing machine are different in

Choose the correct statement