in Theory of Computation reopened by
402 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)$ Only
  2. $(i)$ and $(ii)$ only
  3. $(ii)$ and $(iii)$ only
  4. $(ii)$ only
in Theory of Computation reopened by
402 views

4 Comments

option A is correct.
0
0
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
0
0
Option A
0
0

1 Answer

0 votes
0 votes

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.

Answer:

Related questions