GATE CS 1995 Q2.20 — Context-free Grammars and Push-down Automata

We analyze each definition to see if it generates the language $L = \{x^n y^n \mid n \ge 1\}$:

• Definition I: The context-free grammar $E \rightarrow xEy \mid xy$ has the base case $xy$ ($n=1$). Each recursive application of $E \rightarrow xEy$ adds one $x$ to the left and one $y$ to the right, generating exactly $x^n y^n$ for $n \ge 1$. Thus, Definition I is correct.
• Definition II: The expression $xy \mid (x^+ x y y^+)$ generates strings of the form $x^a y^b$ where $a, b \ge 1$. This includes strings like $x^2 y^3$ where the number of $x$'s and $y$'s are unequal. Thus, it does not generate $L$.
• Definition III: The regular expression $x^+ y^+$ generates all strings with one or more $x$'s followed by one or more $y$'s (i.e., $x^a y^b$ for $a, b \ge 1$). Since the counts of $x$ and $y$ do not have to be equal, it does not generate $L$.

Therefore, only definition I generates the language $L$.