Time Left - 15:00 mins
GATE 2024 Theory of computation Foundation Quiz 41
Attempt now to get your rank among 78 students!
Question 1
Which of the following problem is not decidable?
Question 2
Q is a CFG.
Consider the following problem :
Is L(Q)=∑*?
This problem is ?
Consider the following problem :
Is L(Q)=∑*?
This problem is ?
Question 3
Consider the following languages
is a turing machine that visits state q on some input within 10 steps
is a turing machine, 
where |M| is number of states in machine
Which of the following is correct?
is a turing machine that visits state q on some input within 10 steps is a turing machine, where |M| is number of states in machine Which of the following is correct?
Question 4
Consider the following languages :
L1 : {< M, q > | M is a Turing Machine that visits state q on some input within 15 steps}.
L2 : {< M > | M is a Turing Machine, |M| < 200 where |M|is number of states in machine}.
Which of the following is correct ?
L1 : {< M, q > | M is a Turing Machine that visits state q on some input within 15 steps}.
L2 : {< M > | M is a Turing Machine, |M| < 200 where |M|is number of states in machine}.
Which of the following is correct ?
Question 5
Which of the following is decidable. Assume given a turing machine M a state q, a symbol ‘x’ and a string ‘w’.
- 78 attempts
- 1 upvote
- 0 comments
Apr 22GATE & PSU CS
