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?
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
• 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?
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?
- 327 attempts
- 0 upvotes
- 0 comments
Jul 26GATE & PSU CS