Consider this language:
$K=\{xy \mid x=\{a,b\}^*, y=x^R \text{ or } y=x\}$
I know that these languages are non-regular separately:
$K_1=\{xy \mid x=\{a,b\}^*, y=x^R\}$
$K_2=\{xy \mid x=\{a,b\}^*, y=x\}$
But what about their union?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ There's no rule as such. Provide a DFA/NFA to prove or use the pumping lemma to disprove. $\endgroup$– whoisitFeb 27 at 9:19
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Suppose towards a contradiction that $w$ is regular, let $p$ be its pumping length, and consider the word: $a^pba^pb \in w$.
By the pumping lemma, there is some $k \ge 1$ such that $a^{p + ik}b a^p b \in w$ for all choices of an integer $i \ge -1$. Choosing $i=-1$ we obtain $a^{p-k}b a^p b \in w$. This is a contradiction, therefore $w$ is not regular.
