in Theory of Computation edited by
606 views
1 vote
1 vote

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^{+}$

 

  1. $(i)$
  2. $(i)$ and $(ii)$ only
  3. $(ii)$ and $(iii)$ only
  4. $(ii)$ only
in Theory of Computation edited by
by
606 views

1 comment

The same question asked in GATE CS 1995

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

0
0

2 Answers

0 votes
0 votes
Option A) is correct , only(i) is similar the language.
0 votes
0 votes
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:

Related questions