1
GATE CSE 2002
MCQ (Single Correct Answer)
+2
-0.6
The $$C$$ language is:
A
A context free language
B
A context sensitive language
C
A regular language
D
Parsable fully only by a Turing machine
2
GATE CSE 1997
MCQ (Single Correct Answer)
+2
-0.6
Which one of the following is not decidable?
A
Given a Turing machine $$M,$$ a stings s and an integer $$k,$$ $$M$$ accepts $$s$$ within $$k$$ steps
B
Equivalence of two given Turing machines
C
Language accepted by a given finite state machine is not empty
D
Language generated by a context free grammar is non empty
3
GATE CSE 1994
MCQ (Single Correct Answer)
+2
-0.6
Which of the following conversions is not possible (algorithmically)?
A
Regular grammar to context free grammar
B
Non-deterministic $$FSA$$ to deterministic $$FSA$$
C
Non-deterministic $$PDA$$ to deterministic $$PDA$$
D
Non-deterministic Turing machine to deterministic Turing machine
4
GATE CSE 1992
MCQ (More than One Correct Answer)
+2
-0
In which of the cases stated below is the following statement true?
“For every non-deterministic machine $${M_1}$$ there exists an equivalent deterministic machine $${M_2}$$ recognizing the same language“.
A
$${M_1}$$ is nondeterministic finite automation
B
$${M_1}$$ is a nondeterministic $$PDA$$
C
$${M_1}$$ is a non-deterministic Turing machine
D
For no machine $${M_1}$$ use the above statement true
GATE CSE Subjects
Software Engineering
Web Technologies
EXAM MAP