$\{a^{2n}b^{n+k+1}a^k ∈ \{a, b\}^∗ \mid n \ge 0, k \ge 0\}$
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Please tell us what you have tried. $\endgroup$– NobodyAug 9 at 1:58
-
$\begingroup$ This is unreadable. Use Matjax syntax. $\endgroup$– user16034Aug 10 at 16:14
-
$\begingroup$ My -1 for showing no effort, not even adapting the title of the exercise sheet. $\endgroup$– user16034Aug 10 at 16:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
$L = \{ a^{2n} b^{n+k+1} a^k \mid n,k \ge 0\}$ is not a regular language.
Suppose towards a contradiction that $L$ is regular and let $p$ be its pumping length. Consider the word $b^{p} a^{p-1} \in L$. By the pumping lemma there is some positive integer $i \le p$ such that, for every $h \ge 0$: $$b^{p-i} b^{hi} a^{p-1} \in L.$$ Choosing $h=0$ we obtain: $$b^{p-i} a^{p-1} \in L,$$ which provides the sought contradiction.