# Prove $L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $(mod$ $13) \}$ is regular or context-free or neither

$$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)

so

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?

• – D.W. Feb 9 at 18:58

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.

• 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. – PoliteMan Feb 9 at 20:28
• How pda will be look like? – PoliteMan Feb 9 at 20:43
• 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. – Apass.Jack Feb 9 at 20:58