# is this language regular and why pumping lemma doesn't work?

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?

• Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. – Raphael Sep 28 '18 at 21:15
• It looks like you accidentally submitted your improved version as a new question. What you should do instead is click the "edit" link at the bottom of your question (but above these comments). – Ilmari Karonen Sep 29 '18 at 12:22
• – Gilles Sep 29 '18 at 20:52

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.
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*}
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$$.