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?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Hint: $\Sigma^{*}$ is a regular language for any alphabet $\Sigma$. $\endgroup$– Pseudonym ♦Jun 3, 2022 at 11:35
-
1$\begingroup$ 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. $\endgroup$– D.W. ♦Jun 3, 2022 at 19:22
-
1$\begingroup$ 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". $\endgroup$– D.W. ♦Jun 3, 2022 at 19:39
-
1$\begingroup$ 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. $\endgroup$– D.W. ♦Jun 4, 2022 at 3:25
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
I don't quite understand what you mean by if (A) is decidable then it is a language in R, if you mean that A is regular and B is regular then the intersection of two regular languages is still regular.
However, if you mean that A is decidable and it isn't certainly regular then no. take for example:
$$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).
-
$\begingroup$ How is the intersection not an empty set if B is sigma star? $\endgroup$– nam miJun 3, 2022 at 22:48
-
$\begingroup$ @nammi Because $\Sigma^*$ in this situation is taken to mean all strings over $\{a,b,c\}$, so $A\cap B=A$ $\endgroup$ Jun 4, 2022 at 1:42
-
$\begingroup$ 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... $\endgroup$ Jun 4, 2022 at 12:24