1
$\begingroup$

I am interested in the following questions and would be grateful if anyone could give me hints or point me to articles:

1) Given a regular language $L$, what are its regular sublanguages $L'\subseteq L$, i.e. how to enumerate all regular $L' \subseteq L$ for a given regular language $L$.

2) Could every regular sublanguage $L'$ of a regular language $L$ be written as $L' = L''\cap L$ with $L''$ regular

3) Given a arbitrary language, is it decidable if it is regular (of course one could compute it's syntactic monoid, but this computation could take on forever if the language is not regular)

$\endgroup$
  • 1
    $\begingroup$ 2) can be trivially satisfied by having $L^{\prime \prime} = L^{\prime}$. With a requirement that $L^{\prime} \not = L^{\prime \prime}$, 2) is not satisfied in the case that $L$ is a language of all possible words. (I assumed a fixed alphabet.) $\endgroup$ – bellpeace Oct 19 '13 at 0:29
  • 1
    $\begingroup$ These do not appear to be research-level questions. In 1), what do you mean by "enumerate all regular $L'\subseteq L$"? Specifically, how do you want to enumerate a potentially infinite set of potentially infinite sets? 2) has trivial solutions. In 3), what do you mean by, "Given an arbitrary language"? In what finite form is this potentially infinite set specified? $\endgroup$ – David Richerby Oct 19 '13 at 21:58
  • $\begingroup$ @DavidRicherby: I think that given a regular language, its regular sublanguages are r.e. (see my answer), but perhaps I'm missing something trivial. $\endgroup$ – Marzio De Biasi Oct 19 '13 at 23:02
7
$\begingroup$

3) It is undecidable to know whether a given context-free grammar generates a regular language. So even for context-free languages, you are in trouble.

$\endgroup$
4
$\begingroup$
1) Given a regular language $L$, what are its regular sublanguages $L′\subseteq L$, i.e. how to enumerate all regular $L′\subseteq L$ for a given regular language $L$.

If $L, L'$ are regular languages, then $L' \subseteq L$ is decidable (it is PSPACE-complete, see A. R. Meyer L. J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space.). So you can just enumerate the regular expressions over the alphabet of $L$ in lexicographic order (i.e. enumerate the regular languages): $L_1, L_2, ...\,$; if $L_i \subseteq L$ then output $L_i$ as the next element of the enumeration, otherwise discard it. All and only those regular languages that are subsets of $L$ are included in the enumeration.

$\endgroup$
  • $\begingroup$ You've used the fact that $L'\subseteq L$ is decidable in PSPACE to derive the much weaker result that $L'\subseteq L$ is recursively enumerable. $\endgroup$ – David Richerby Oct 20 '13 at 7:39
  • $\begingroup$ @DavidRicherby: the OP asks for an enumerator for the regular languages that are subset of $L$. What is the wrong part of my proof? Regular languages are recursively enumerable; just run an enumeration of them and for every $L_i$ regular, check if it is a subset of $L$ (decidable), if it is a subset then output it, otherwise continue. The result is an enumerator for the regular languages that are subsets of $L$, isn't it? Every $L'_i$ regular that is a subset of $L$ is included in the enumeration. $\endgroup$ – Marzio De Biasi Oct 20 '13 at 9:41
  • $\begingroup$ It's certainly correct. And, since there are infinitely many regular sublanguages of an infinite regular language, you can't actually do better than this. $\endgroup$ – David Richerby Oct 20 '13 at 10:37
  • $\begingroup$ @DavidRicherby: if it is correct, why it doesn't answer point (1) of the question? $\endgroup$ – Marzio De Biasi Oct 20 '13 at 10:40
  • $\begingroup$ As far as I can see, it does answer part 1. You could add to your answer the observation that it's essentially best-possible and then we could delete these comments. (A side-effect is that, if you edit your answer, I can undo my downvote.) $\endgroup$ – David Richerby Oct 20 '13 at 10:47
2
$\begingroup$

1) I'll let someone wiser and clearer answer this.

2) Yes and no? Allow me to explain and come to your own conclusion.

There is always the trivial L'' = L' and sometimes this is the only answer. If the alphabet is E and L = E*, then the only L'' that will intersect with L to give L' is L'. (there are less extreme versions of this, say if L'={}, no matter the L, L'==L'')

If you wanted to see if there are any non-trivial solutions, you can express L' as an DFA A' which is a subautomaton of A, a possibly non-minimal DFA equivalent to L. Whenever you can add an edge in A' that is not in A, you have a needed L''. If there is no such edge to add, then there is only the trivial solution. (This operation would be equivalent to finding any word w=se where w is in E*\L and s is in L')

3) How am I given it? Could you provide an example? If I am given it as a grammar/expression, I'd use the pumping lemma. If I am given it as an unambiguous English statement, I'd translate it to an expression then use the pumping lemma.

$\endgroup$
1
$\begingroup$

I am not sure about (i).

As for (ii), as pointed out in the comments, we can see that the language $L'' = L$ satisfies the requirement. Also, we can construct smaller sublanguages.

Let $L_1 = L-L'$ we know that $L_1 \neq \phi$. Consider the regular language $L''=L-a$ where $a$ is the lexicographically smallest string in $L_1$. This language is still regular and also contains the language $L'$.

In part (iii) we can use Rice's Theorem to show that if a language is represented as a Turing Machine than the language is not decidable. If it was represented as a regular expression or a DFA/NFA then the language is regular.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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