NIELIT 2017 OCT Scientific Assistant A (CS) - Section B: 31

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)$
• B. $(i)$ and $(ii)$ only
• C. $(ii)$ and $(iii)$ only
• D. $(ii)$ only

Comments

The same question asked in GATE CS 1995

Link: https://gateoverflow.in/2632/gate1995-2-20

Answer 1

Option A) is correct , only(i) is similar the language.

Answer 2

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.}$

​​​​​​​