GATE 2020 : Theory of Computation Quiz 3

Attempt now to get your rank among 610 students!

Question 1

Let L is reverse of w}. Then which of the following grammar generates L.

• A
  
• B
  
• C
  
  
• D
  
  

Question 2

Consider the following grammar.

Identify the language generated by above CFG?

• A
• B
• C
• DNone of these

Question 3

The CFG equivalent to the following PDA is
M = { {, }, {0}, {R}, 𝛿, , R, ∅}
Where : 𝛿(, 0, R) = {(, R)}
(, 0, R) = {(, R)}
(, €, R) = {(, €)}

• AS → {, R, }
  [, R, ] → 0[, R, ]
  [, R, ] → 0[, R, ] | €
• BS → {, R, }
  [, R, ] → 0[, R, ]
  [, R, ] → 0[, R, ] | €
• CS → [, R, ] [, R, ]
  [, R, ] → 0[, R, ]
  [, R, ] → 0[, R, ]
  [, R, ] → € | 0
  [, R, ] → 0[, R, ]
• DS → {, R, }
  [, R, ] → 0[, R, ]
  [, R, ] → 0[, R, ]

Question 4

Consider the following PDA with transitions.


Which one of following languages is accepted by above PDA with transitions? (Assume w^R is reverse of w)

• A
• B
• C
• D

Question 5

The language generated by the following grammar over the alphabet {a, b} can be described as the set of ____
               S →  aSa | bSb | a | b

• Aall palindromes.
• Ball odd length palindromes.
• Cstrings that begin and end with the same symbol.
• Dall even length palindromes.

Question 6

Consider the transition diagram of a PDA given below with input alphabet and stack alphabet Z is the initial stack symbol. Let L denote the language accepted by the PDA.

Which one of the following is TRUE?

• A and is not accepted by any finite automata
• B and is not accepted by any deterministic PDA
• CL is not accepted by any Turing machine that halts on every input
• D and is deterministic context-free

• 610 attempts
• 6 upvotes
• 3 comments