0
$\begingroup$

Is this regular or not

L = {w1w^R | w ∈ {0,1}* (where for any word w ∈ {0,1})*, w^R denotes the reverse of w)

$\endgroup$
1
  • $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    Oct 1 '20 at 17:27
0
$\begingroup$

L is not a regular language.

We can contradict by pumping lemma for regular languages.

Let assume L is regular, so there exists an integer $ k $ of pummping lemma.

$ w = a^kb $

$ w^R = ba^k $

$ ww^R = a^kbba^k \in L $

$ w' = a^{k-r}bba^k \notin L , r>0 $

Contradiction to $ w' \in L $.

$\endgroup$
1
  • $\begingroup$ Actually in this case you can pump $bb$ and there is no problem. $\endgroup$
    – user253751
    Oct 1 '20 at 17:52

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