GATE 2024 Theory of computation Foundation Quiz 89

Given the following two grammars:

G₁: S → AB | aaB
      A → a | Aa
      B → b

G2:  S → aSbS | bSaS | ϵ

Which statement is correct?

What is the language recognized by the following regular grammar?

G:

S → aA|bS

A → bB|aS

B → dB|ϵ|aS

Consider the following languages:

L₁ = {aⁿwaⁿ | w ∈ {a, b}*}

L₂ = {wxw^R | w, x ∈ {a, b}*, |w|,|x|>0}

Note that w^R is the reversal of the string w. Which of the following is/are TRUE?

Which of the following is both DCFL and regular?

Consider the following languages:

L₁: = {aⁱ b^j c^k | i = j, j < k}

L₂: = {aⁱ b^j c^k | (i ≤ j) or (j ≤ i), j = k}

L₃: = {a^m bⁿ cⁿ d^m | m ≠ n}

L₄: = {aⁱ b^j c^k | if (i = j) then k is even}

The number of the above languages L₁, L₂, L₃ and L₄ are context-free languages is ____.