# Decidability of intersection of regular and decidable languages

I'm wondering if a language (A) is a decidable language and language (B) is a regular language, is the intersection between A and B regular?

• Hint: $\Sigma^{*}$ is a regular language for any alphabet $\Sigma$. Commented Jun 3, 2022 at 11:35
• Please don't delete your question after receiving an answer. Part of our mission is to build up an archive of knowledge, by creating an archive of high-quality questions and answers that will be useful not only to you but to others in the future. Some may consider it impolite to delete your question after receiving an answer, as that prevents others from benefiting from the answer, and the answerer might have been answering on that basis.
– D.W.
Commented Jun 3, 2022 at 19:22
• Please don't edit your question in a way that makes it harder to understand. Please don't use non-standard abbreviations like "dec", "reg", "inters".
– D.W.
Commented Jun 3, 2022 at 19:39
• Please don't edit the question to change the question after receiving an answer. If you have a new question (is the intersection decidable) please post a new question to ask that one.
– D.W.
Commented Jun 4, 2022 at 3:25

$$A=\{a^nb^nc^n\ |\ n\geq0\}$$ $$B=\Sigma^*$$
Note that A is a decidable language using a Turing machine, I assume you know this already, otherwise, you can simply achieve a proof for it, it's a well-known example for a language that is not context-free. Moreover, B is a regular language and the intersection between both is: $$A\cap B=\{a^nb^nc^n\ |\ n\geq0\}$$ which is still not a regular language (note that since it's not a context-free language then it's certainly not a regular language).
• @nammi Because $\Sigma^*$ in this situation is taken to mean all strings over $\{a,b,c\}$, so $A\cap B=A$ Commented Jun 4, 2022 at 1:42
• As @RickDecker stated every intersection of a language $L$ with $\Sigma^*$ is still $L$, Please look at the definition of the Kleene Star, and then you can know what $\Sigma^*$ means. Briefly, $\Sigma^*$ is the language that contains every word that can be consisted of the letters in the alphabet $\Sigma$, hence, if $\Sigma=\{0,1\}$ then $\Sigma^*$ is the language that contains all the strings that can be consisted of 0 and 1, for example, $\varepsilon$ (the empty string that contains 0 letters), 0, 1, 01, 11, 100, 101, 110, 111, 00000101010, 101010100001... Commented Jun 4, 2022 at 12:24