Register

GATE CSE 1995 | Question: 2.20

• recategorized by
10,682 views
32 votes
32 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

• recategorized by
User Avatar

8 Answers

Best answer
37 votes
37 votes

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
User Avatar
4 votes
4 votes
A is the answer B is wrong because xxyyy is there same apply for C also
User Avatar
1 votes
1 votes

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

User Avatar
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
User Avatar
Page:
Voting & Accepting an answer helps improve the community
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

26 votes
26 votes
5 answers
1
Kathleen asked Oct 8, 2014
15,909 views
GATE CSE 1995 | Question: 2.24
Let $\Sigma=\left\{0,1\right\}, L = \Sigma^*$ and $R=\left\{0^n1^n \mid n > 0\right\} $ then the languages $L \cup R$ and $R$ are respectively regular, regular not regular, regular regular, not regular not regular, not regular
Let $\Sigma=\left\{0,1\right\}, L = \Sigma^*$ and $R=\left\{0^n1^n \mid n 0\right\} $ then the languages $L \cup R$ and $R$ are respectivelyregular, regularnot regular, ...
User Avatar
49 votes
49 votes
7 answers
3
Kathleen asked Oct 8, 2014
38,325 views
GATE CSE 1995 | Question: 2.21
The postfix expression for the infix expression $A+B*(C+D)/F+D*E$ is: $AB + CD + *F/D +E*$ $ABCD + *F/DE* ++$ $A * B + CD/F *DE ++$ $A + *BCD/F* DE ++$
The postfix expression for the infix expression $A+B*(C+D)/F+D*E$ is:$AB + CD + *F/D +E*$$ABCD + *F/DE* ++$$A * B + CD/F *DE ++$$A + *BCD/F* DE ++$
User Avatar
25 votes
25 votes
4 answers
4
Kathleen asked Oct 8, 2014
7,718 views
GATE CSE 1995 | Question: 2.5
What values of $A, B, C$ and $D$ satisfy the following simultaneous Boolean equations? $\overline{A} + AB =0, AB=AC, AB+A\overline{C}+CD=\overline{C}D$ $A=1, B=0, C=0, D=1$ $A=1, B=1, C=0, D=0$ $A=1, B=0, C=1, D=1$ $A=1, B=0, C=0, D=0$
What values of $A, B, C$ and $D$ satisfy the following simultaneous Boolean equations?$\overline{A} + AB =0, AB=AC, AB+A\overline{C}+CD=\overline{C}D$$A=1, B=0, C=0, D=1$...
User Avatar
Link Copied!