3
$\begingroup$

Consider the following problem:

Is $L_1 * L_2$ is of $LType$?

where we know that both $L_1$ and $L_2$ are of type $LType$ and $LType$ is closed under $*$ operation.

Above, by $LType$, I mean any type of language that is known to belong to any type of Chomsky hierarchy. So it may be regular (Chomsky Type 3), CFL or DCFL (Chomsky Type 2) etc. Also by operation $*$, I mean any binary operation that results in another language, say intersection $\cap$, union $\cup$, difference $-$ etc.

Given all these pre-information of the type of languages and their closure under the specified operation, is the above problem decidable? For example

Does the problem:

"Given that $R_1$ and $R_2$ are regular, is $R_1 \cap R_2$ too a regular language?"

is decidable, especially when we know that regular languages are closed under intersection?

Also can we comment in the same manner about undecidability of operation when we know that the type of operand languages is not closed under that operation? That is

Does the problem

Is $L_1*L_2$ is of $LType$?

is undecidable?, especially when we know that $LType$ is not closed under the operation $*$ and that $L_1$ and $L_2$ are of type $LType$?

For example

Does the problem

Is $CFL_1\cap CFL_2$ is CFL?

is undecidable?, especially when we know that CFLs are not closed under intersection.

I feel both of above facts are correct/obvious/intuitive. But I am confused because no book on the theory of automata states it clearly.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

If a family $\mathcal F$ of languages is closed under some operation, say intersection, then you are right that it is decidable whether the intersection of any two particular languages from $\mathcal F$ also belongs to $\mathcal F$. The answer is always Yes.

The converse, however, isn't true. Consider the family $\mathcal F_m$ of all regular languages which are accepted by some DFA having at most $m$ states, for some parameter $m$. When $m > 1$, this language family isn't closed under intersection, but given any two languages from $\mathcal F_m$ (in any reasonable encoding), it is decidable (depending on the encoding, efficiently) whether their intersection belongs to $\mathcal F_m$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ If I am not interpreting it wrong, $\mathcal F_m=\mathcal R_1 \cup \mathcal R_2 \cup ...\cup \mathcal R_m$ and regular languages are closed under union. So, $\mathcal F_m$ should also be regular, thus $\mathcal F_m$ should also be closed under the intersection (as regular languages are closed under intersection). $\endgroup$
    – Mahesha999
    Dec 24, 2016 at 13:56
  • $\begingroup$ ohh..just now came across this problem and its solution while solving online test-series. Is the answer given to the problem wrong? or does not imply: if a family of languages is not closed under particular operation, then the question of whether performing that operation on two languages from that family result in another language belonging to the same family is undecidable? $\endgroup$
    – Mahesha999
    Dec 24, 2016 at 17:39
  • $\begingroup$ @Mahesha999 The answer is correct but the explanation is really bad. Since the other types are closed under intersection, the problem is decidable for them. This process of elimination shows that the only possible answer is B. $\endgroup$
    – Yuval Filmus
    Dec 24, 2016 at 20:15
  • $\begingroup$ Regarding $\mathcal{F}_m$, for $m > 1$ it is not closed under intersection. For example, $(aa)^*,(aaa)^* \in \mathcal{F}_3$ but $(aa)^* \cap (aaa)^* = (aaaaaa)^* \notin \mathcal{F}_3$. A more generic example is the language $L_{m,a}$ of all words in which the number of occurrences of the symbol $a$ is a multiple of $m$. Clearly $L_{m,a} \in \mathcal{F}_m$, but for $m>1$ and $a \neq b$, $L_{m,a} \cap L_{m,b} \notin \mathcal{F}_m$. A tight example over the unary alphabet is $a(a^{m-1})^*,(a^m)^* \in \mathcal{F}_m$, $a(a^{m-1})^* \cap (a^m)^* \notin \mathcal{F}_m$. $\endgroup$
    – Yuval Filmus
    Dec 24, 2016 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.