Which of the following definitions below generates the same language as L,…
1995
Which of the following definitions below generates the same language as L, where
L = { xⁿ yⁿ such that n ≥ 1 }
I. E → xEy | xy
II. xy | (x⁺ s y y⁺)
III. x⁺ y⁺
- A.
I only
- B.
I and II
- C.
II and III
- D.
II only
Attempted by 9 students.
Show answer & explanation
Correct answer: A
The target language L consists of strings with equal numbers of x's followed by y's where n is at least 1. Grammar I (E → xEy | xy) generates exactly this pattern through recursive expansion. Grammar III allows unequal counts, and Grammar II contains undefined symbols.
A video solution is available for this question — log in and enroll to watch it.