Time Left - 12:00 mins

Theory of Computation : Nuclear Quiz 1

Attempt now to get your rank among 327 students!

Question 1

Consider the following NFA.

Which of the following regular grammar is equivalent to the above NFA?

Question 2

Any string of terminals that can be generated by the following CFG satisfy which of the given choices?

S → XY

X → aX | bX | a

Y → Ya | Yb | a

Question 3

A language accepted by a pushdown automaton in which stack size is limited to 100 is best described as?

Question 4

If L and

are recursively enumerable then L is

Question 5

Assume there are (n + 2) languages over the same input alphabet Σ used in the composition with union as follows and result is represented by Y.

Given that A = Σ* and B = Φ. All languages are defined over the same alphabet Σ={a, b}. What is the language represented by Y?

Question 6

Which of the following is True?

Question 7

Identify Regular Language from the following

Question 8

Consider the three problems :
• Equivalence
• Ambiguity
• Regularity

Question 9

Consider the following grammar G:
S → aXa⎪bXb⎪a⎪b
X → aX⎪bX⎪ε
Identify the language generated by the above G?

Question 10

Consider the following statements about a TM that accepts a language L.

S1: If the string in the language L, then TM halts in final state.

S2: If the string not in the language L, then TM may halt in non-final state or never halt.

If the string given as an input to the TM, then which of the above statements are correct?

Tags :

Jul 26GATE & PSU CS