0
$\begingroup$

I was told that this language is regular but as I can show below, pumping lemma is not working for it. What am I doing wrong? Is this language really regular? Why? enter image description here

$\endgroup$
6
$\begingroup$

Your use of the pumping lemma is incorrect. First, to show that the pumping lemma fails to hold in the case of your string $S$ (and thereby prove $L$ non-regular), you would have to show that every choice of $y$ fails. You've picked a specific $y$.

Second, $S'$ is in $L$. Simply take the whole $S'$ string as $b$ and let $a$ be empty. Every string of zeros and ones is in $L$ the same way, so $L = \{0, 1\}^*$ and $L$ is regular.

$\endgroup$
8
$\begingroup$

It's a "trick" question. The language is regular because \begin{align*} \{aba^{\mathrm{R}}\mid a,b\in\{0,1\}^*\} &= \big\{\varepsilon b\varepsilon^{\mathrm{R}}\mid b\in\{0,1\}^*\big\} \cup \big\{a b a^{\mathrm{R}}\mid a\in\{0,1\}^+,\ b\in\{0,1\}^*\big\}\\ &= \{0,1\}^* \cup \big\{a b a^{\mathrm{R}}\mid a\in\{0,1\}^+,\ b\in\{0,1\}^*\big\}\\ &= \{0,1\}^*\,. \end{align*}

$\endgroup$
  • $\begingroup$ But then there must be something wrong in the solution given in the question? $\endgroup$ – rus9384 Sep 28 '18 at 22:06
  • $\begingroup$ @rus9384 Yes, as shown in Daniel Mroz's answer. $\endgroup$ – David Richerby Sep 28 '18 at 22:46
6
$\begingroup$

Write the word $s'$ as

$$ s' = 0^{(p-\beta)} \left(1^p01^p0^{\beta} \right)0^{(p -\beta)} $$ to see that it is in fact in $L$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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