Theory of Computation and Compilers – Previous Year Questions
250 questions from past UGC NET Paper 2 – Computer Science papers, each with the correct answer. Open any question for its explanation.
- Two finite state machines are said to be equivalent if they :
- The finite state machine given in figure below recognizes :
- A pushdown automata behaves like a Turing machine when the number of auxiliary memory is :
- Pushdown automata can recognize language generated by_________.
- To obtain a string of n Terminals from a given Chomsky normal form grammar, the number of productions to be used is :
- Consider the two grammars: G₁: S → SbS | a G₂: S → aB | ab, A → AAB | a, B → ABb | b Which of the following options is correct?
- Context-sensitive language can be recognized by a :
- The set A= { 0n1n2n | n= 1, 2, 3,..............} is an example of a grammar that is :
- A bottom-up parser generates :
- Consider the statements: S₁: There exists no algorithm for deciding whether any two Turing machines M₁ and M₂ accept the same language. S₂: The problem of determining whether a Turing machine halts on any input is undec…