in Theory of Computation recategorized by
8,433 views
30 votes
30 votes

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

    1. I only

    2. I and II

    3. II and III

    4. II only

in Theory of Computation recategorized by
8.4k views

4 Comments

@teluguenglish,

when n=1,string would be ''xy",

and in (Ⅰ),you can get "xy" because"xy" given as stopper.
0
0
Nice approach
0
0

@vaibhav101 Just to add something to your logic, L is Context Free but not regular.

0
0

8 Answers

34 votes
34 votes
Best answer

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.

edited by
4 votes
4 votes
A is the answer B is wrong because xxyyy is there same apply for C also
1 vote
1 vote

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

0 votes
0 votes
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:

Related questions