Time Left - 15:00 mins
GATE Prev Year : Theory of Computation Test-6
Attempt now to get your rank among 520 students!
Question 1
Which of the following statements are true?
Question 2
If L and 
are recursively enumerable then L is
are recursively enumerable then L isQuestion 3
Let G = ({S},{a,b},R,S) be a context free grammar where the rule set R is S → a S b | S S | ε
Which of the following statements is true?
Which of the following statements is true?
Question 4
The finite state machine described by the following state diagram with a as starting state, where an arc label is
and x stands for 1-bit input and y stands for 2-bit output
and x stands for 1-bit input and y stands for 2-bit output Question 5
Let L = L1∩ L2, where L1 and L2 are languages as defined below:
L1 = {am bm c an bn | m,n>=0}
L2 = {ai bj ck | i,j,k>=0}
Then L is
L1 = {am bm c an bn | m,n>=0}
L2 = {ai bj ck | i,j,k>=0}
Then L is
Question 6
Consider the following statements about the context free grammar
G ={S → SS, S → ab, S → ba, S → ∈}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?
G ={S → SS, S → ab, S → ba, S → ∈}
I. G is ambiguous
II. G produces all strings with equal number of a’s and b’s
III. G can be accepted by a deterministic PDA.
Which combination below expresses all the true statements about G?
- 520 attempts
- 1 upvote
- 24 comments
Jul 5GATE & PSU CS
