WorksheetsTOC_CO4&CO5
Total questions: 25
Worksheet time: 13mins
A Turing machine that is able to simulate other Turing machines:
Nested Turing machines
Universal Turing machine
Counter machine
None of the mentioned
Which of the problems are unsolvable?
Halting problem
Boolean Satisfiability problem
Halting problem & Boolean Satisfiability problem
None of the mentioned
Which of the following a Turing machine does not consist of?
input tape
head
state register
none of the mentioned
The value of n if Turing machine is defined using n-tuples:
6
7
8
5
If d is not defined on the current state and the current tape symbol, then the machine ______
does not halts
halts
goes into loop forever
none of the mentioned
Statement: Instantaneous descriptions can be designed for a Turing machine. State true or false:
true
false
Which of the following are the models equivalent to Turing machine?
Multi tape Turing machine
Multi track Turing machine
Register machine
All of the mentioned
A language L is said to be Turing decidable if:
recursive
TM recognizes L
TM accepts L
recursive & TM recognizes L
The class of recursively enumerable language is known as:
Turing Class
Recursive Languages
Universal Languages
RE
Which of the following statements are false?
Every recursive language is recursively enumerable
Recursively enumerable language may not be recursive
Recursive languages may not be recursively enumerable
None of the mentioned
Choose the correct option: Statement: If L1 and L2 are recursively enumerable languages over S, then the following is/are recursively enumerable.
L1 U L2
L2 ∩ L2
Both L1 U L2 and L2 ∩ L2
None of the mentioned
If L is a recursive language, L' is:
Recursive
Recursively Enumerable
Recursive and Recursively Enumerable
None of the mentioned
Choose the appropriate option: Statement: If a language L is recursive, it is closed under the following operations:
Union
Intersection
Complement
All of the mentioned
A recursively enumerable language L can be recursive if:
L' is recursively enumerable
Every possible sequence of moves of T, the TM which accept L, causes it to halt
L' is recursively enumerable and every possible sequence of moves of T, the TM which accept L, causes it to halt
None of the mentioned
A language L is recursively enumerable if L=L(M) for some turing machine M. Which among the following cannot be among A, B and C?
yes w ∈ L
no w ∉ L
M does not halt w ∉ L
None of the mentioned
A language L is recursively enumerable if L=L(M) for some turing machine M. Which among the following cannot be among A, B and C?
yes w ∈ L
no w ∉ L
M does not halt w ∉ L
None of the mentioned
A Language L may not be accepted by a Turing Machine if:
It is recursively enumerable
It is recursive
L can be enumerated by some turing machine
None of the mentioned
Which of the following can accept even palindrome over {a, b}
Push down Automata
Turing machine
NDFA
All of the mentioned
Which of the functions can a turing machine not perform?
Copying a string
Deleting a symbol
Accepting a pal
Inserting a symbol
Halting state of Turing machine are:
Start and stop
Accept and reject
Start and reject
Reject and allow
Which of the following statement is wrong?
Every recursive language is recursively enumerable
A language is accepted by FA if and only if it is context free
Recursive languages are closed under intersection
A language is accepted by FA if and only if it is right linear
Recursively enumerable languages are not closed under
(a)
Recursively enumerable languages are not closed under
(a)
Which of the following statement is true?
All languages can be generated by CFG
Any regular language has an equivalent CFG
The class of CFG is not closed under union
Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?
L1' --> Complement of L1
L2' --> Complement of L2
L1' is recursive and L2' is recursively enumerable
L1' is recursive and L2' is not recursively enumerable
L1' and L2' are recursively enumerable
