NIELIT 2017 OCT Scientific Assistant A (IT) - Section C: 9

Question

Which of the following definitions generates the same languages as $L,$ where

$L = \{x^{n}y^{n},n \geq 1\}$

1. $E \rightarrow xEy \mid xy$
2. $xy \mid x^{+}xyy^{+}$
3. $x^{+}y^{+}$

 

• A. $(i)$ Only
• B. $(i)$ and $(ii)$ only
• C. $(ii)$ and $(iii)$ only
• D. $(ii)$ only

Comments

option A is correct.

---

option A is correct because the other option i.e. b and c giving us the choice to generate no x’s or no y’s

---

Option A

---

https://gateoverflow.in/336889/Nielit-2017-oct-scientific-assistant-a-cs-section-b-31

Answer 1

We need to have

1. equal number of x and y, also
2. no x can come after y occurs.

1. We can ensure equal number of x and y, also requirement 2 is followed.

2,3. We have $x^+$ and $y^+$, no way to ensure equal number of x and y.

So A is correct.