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

Whatever we do with statement we always have a^nb^n but for other options we can't do the same.

---

There should be equal number of x and y, which only 1st option satisfies ,because other 2 options can generate unequal number of x and y.

---

2 and 3 can generate any no. of x follwed by any no. of y
 

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.

Comments

perfect, thanks

Answer 2

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

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

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 5

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

Answer 6

(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.