1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ There's no rule as such. Provide a DFA/NFA to prove or use the pumping lemma to disprove. $\endgroup$
    – whoisit
    Feb 27, 2023 at 9:19

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.