Skip to main content
added 191 characters in body
Source Link

$ 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}$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 but.:

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?

$ 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 but.. Any idea?

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

Source Link

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 but.. Any idea?