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$
  • 5
    $\begingroup$ Note that you can use LaTeX here to typeset mathematics in a more readable way. See here for a short introduction. $\endgroup$ – Raphael Sep 28 '18 at 21:15
  • 2
    $\begingroup$ 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). $\endgroup$ – Ilmari Karonen Sep 29 '18 at 12:22
  • 1
    $\begingroup$ Please do not post a screenshot or photo of text. $\endgroup$ – Gilles Sep 29 '18 at 20:52
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.