Q4.Let A and B be infinite alphabets and let # be a symbol outside both A and B. Let f be a total
functional from A*
to B*
. We say f is computable if there exists a Turning machine M which
given an input x in A*
, always halts with f(x) on its tape. Let Lf denote the language
{x#f(x)|x∈A*}. Which of the following statements is true:
Answer : Option AExplaination / Solution:
A TM is recursive iff it halts for every input string (either in accept or reject state).
Here, a computable function is defined in a similar way.
Q6.Let L1 be a recursive language. Let L2 and L3 be languages that are recursively
enumerable but not recursive. Which of the following statements is not
necessarily true?
Answer : Option BExplaination / Solution: No Explaination.
Q8.Let L = {w ∈ (0 + 1)* | w has even number of 1s}, i.e. L is the set of all bit strings
with even number of 1s. Which one of the regular expressions below represents
L?
Answer : Option AExplaination / Solution: No Explaination.
Q9.Consider the languages L1 = {0i1j | i≠j}. L2 = {0i1j | i=j}. L3 = {0i1j | i=2j+1}. L4 = {0i1j | i≠2j}. Which one of the following statements is true?
Answer : Option AExplaination / Solution: No Explaination.
Q10.Let w be any string of length n in {0, 1}*. Let L be the set of all substrings of w.
What is the minimum number of states in a non-deterministic finite automaton
that accepts L?
Answer : Option BExplaination / Solution: No Explaination.
Total Question/Mark :
Scored Mark :
Mark for Correct Answer : 1
Mark for Wrong Answer : -0.5
Mark for Left Answer : 0