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

(I) is the correct definition and the other two is wrong because the other two can have any no. of x and y. There is no such restriction over the number of both being equal.

Answer 2

In 2ND OPTION, least length string can be xxyy, but we can generate a string as xy according to question so rejected. 

In 3^rd option, number of x and y can vary but here as per the grammar given in question we are getting equal nos. of x and y.

So only option 1 gives correct result.

Answer 3

The language $L=\{x^ny^n \text{such that }n\geq 1\}$ has following set of strings:

$L=(xy,xxyy,xxxyyy…….\infty)$

1) $E\rightarrow xEy \mid xy$: This grammar can generate all possible string which is generated by language $L.$

 Following strings can be generated by the above grammar: $xy,xxyy,xxxyyy….\infty$  

so this option is correct.

​​​​​​​2) $xy\mid x^+xyy^+$: the minimum length of the string that can be generated by this regular expression is $xy$. it can generate all the string which is generated by language $L$ but it can also generate additional string which is not generated by language $L$ such as $xxxyy,xxyyy$. these are invalid strings for language $L.$

so this option is wrong here.

​​​​​​​3) $x^+y^+$: this regular expression generate strings like $xy,xxy,xyy,xxxy,xyyy….\infty$ which is not generated by language $L.$

so this option is also wrong.

$\therefore \text{Option A is correct.}$

Answer 4

Grammar 1 generates exact same language.

Grammar 2 & 3 CAN generate all the strings of the given language but it CAN also generate other strings that doesn't belongs to L. Hence Option A is correct.