GATE CSE 1995 | Question: 2.20

Question

Which of the following definitions below generate the same language as $L$, where $L=\{x^ny^n \text{ such that } n\geq 1 \}$?

1. $E \rightarrow xEy\mid xy$

2. $x y \mid (x^+xyy^+$)

3. $x^+y^+$

   • A. I only

   • B. I and II

   • C. II and III

   • D. II only

Comments

@teluguenglish,

when n=1,string would be ''xy",

and in (Ⅰ),you can get "xy" because"xy" given as stopper.

---

Nice approach

---

@vaibhav101 Just to add something to your logic, L is Context Free but not regular.

Answer 1

Correct Option: A

In the other two you can have any number of $x$ and $y$. There is no such restriction over the number of both being equal.

Answer 2

A is the answer B is wrong because xxyyy is there same apply for C also

Answer 3

given language L is CFL , so we can not write a regular expression for this. but in option ii,iii it is written in regular expression so it is clearlly false.  so option a is true

Answer 4

from the very easy eye We can say that i and iii are correct as n>=1 but as there is no opt so 1 is correct A