I'm practicing for my CS exam and I got stuck on following language $L:= \{ a^{k} b u a^{k} | k \geq 1, u \in \Sigma^{*}\}$
$\Sigma = \{a,b\}$
I've tried to prove this language using a pumping lemma, not sure if it's the best way to prove the irregularity. I don't think I got far enough to have a strong solution.
$w = a^pbu^pa^p$
$|w| = 3p \geq p$
Which then gives me $xy^2z = a^{n+k}bu^na^n$
But I'm not sure how to proceed from here. This is the I've gone through examples like $0^n1^m$ etc. but this one seems to be a bit more complicated for me. Any help would be highly appreciated
Note that $u$ in the definition of $L$ is in $\Sigma^*$, not $\Sigma$, so your $u^p$ in your definition of $w$ doesn’t actually specify anything in particular. I would simply take $w=a^pba^p$, where $p$ is the pumping length. If $L$ is regular, there is a decomposition $w=xyz$ such that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for all $k\ge 0$. This means that $xy$ is contained in the first block of $p$ $a$s, so there are integers $r\ge 0$ and $s\ge 1$ such that $x=a^r$, $y=a^s$, and $r+s\le p$. It follows that $z=a^{p-r-s}ba^p$ and hence that
$$xy^kz=a^r(a^s)^ka^{p-r-s}ba^p=a^{p+(k-1)s}ba^p\,.$$
This is in $L$ if and only if $p+(k-1)s=p$, which is true if and only if $k=1$. That is, $k=1$ is the only value of $k$ for which $xy^kz\in L$, whereas if $L$ were regular, $xy^kz$ would be in $L$ for every $k\ge 0$. This shows that $L$ cannot be regular.