$ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $

Exercises: If the language L is regular (build a DFA or regular expression) else if the language L is context-free (build a grammar or PDA) else if the language L is not context-free (Prove)


We know that $ww ^ {R}$ without any restrictions isn't regular, but it is context-free. but with additional above restrictions $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ I have no idea how to prove this. I think this language still isn't regular :

Let's take $n, m > p$ where $p$ is from pumping lemma and $n mod 13 = 0$ and $m mod 13 = 0$ and chose word $s = a^{m}b^{n}b^{n}a^{m}$ and use the pumping lemma that is not regular. Well?

Any idea?


Let $$ P = \{ww^{R} : w\in \{a, b\}^{*} \} $$ $$R_a=\{u\in \{a, b\}^{*} : |u|_{a}\equiv 0\ (\text{mod}13) \} $$ $$R_b=\{u\in \{a, b\}^{*} : |u|_{b}\equiv 0\ (\text{mod}13) \} $$

We know $P$ is context-free.

We know $R_a$ is regular and $R_b$ is regular. So $R_a\cap R_b$ is regular.

So, $L=P\cap (R_a\cap R_b)$ is context-free.

Exercise 1. (One minute or less) Verify that $L=P\cap (R_a\cap R_b)$.

Exercise 2. Show that $R_a$ is regular.

| cite | improve this answer | |
  • 1
    $\begingroup$ Exercise 1. R_a \cap R_b is regular because two regular language are close under intersection and P is context-free. We know that context-free \cap regular is context-free. context-free are closed under intersection of context free with regular languages. $\endgroup$ – PoliteMan Feb 9 '19 at 20:28
  • $\begingroup$ How pda will be look like? $\endgroup$ – PoliteMan Feb 9 '19 at 20:43
  • $\begingroup$ There is a construction of pda from the pda of a context-free language and the dfa of a regular language. Since we have palindromes, the pda must be a npda. $\endgroup$ – John L. Feb 9 '19 at 20:58

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.