<p>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.</p>

CC BY-SA 3.0
2013-10-19T14:47:26.050Z
2013-10-19T14:47:26.050Z
J.-E. Pin
<blockquote>
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$.
</blockquote>

<p>If $L, L'$ are regular languages, then $L' \subseteq L$ is decidable (it is PSPACE-complete, see <a href="http://dl.acm.org/citation.cfm?id=1438639" rel="nofollow">A. R. Meyer  L. J. Stockmeyer, The equivalence problem for regular expressions with squaring requires exponential space.</a>).
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.</p>

CC BY-SA 3.0
2013-10-20T07:39:32.713Z
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.
David Richerby
CC BY-SA 3.0
2013-10-20T09:41:11.487Z
@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.
Marzio De Biasi
CC BY-SA 3.0
2013-10-20T10:37:11.207Z
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.
David Richerby
CC BY-SA 3.0
2013-10-20T10:40:33.523Z
@DavidRicherby: if it is correct, why it doesn't answer point (1) of the question?
Marzio De Biasi
CC BY-SA 3.0
2013-10-20T10:47:05.313Z
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.)
David Richerby
CC BY-SA 3.0
2013-10-20T11:06:00.183Z
@DavidRicherby: ok, but I don't understand what you mean with "it's essentially best-possible" ? Do you mean that it is a weak result ? (I included the PSPACE reference only for pedantry, but the important fact in the (trivial) proof is that inclusion is decidable for regular languages)
Marzio De Biasi
CC BY-SA 3.0
2013-10-20T11:40:16.460Z
It felt weak because you've gone from "decidable in PSPACE" to "recursively enumerable". However, since the answer can be infinite, we can't hope for a "nice" answer like, "It's in double-exp-space".
David Richerby
CC BY-SA 3.0
2013-10-19T10:10:00.640Z
2013-10-20T11:04:29.847Z
2013-10-20T11:04:29.847Z
Marzio De Biasi
<p>1) I'll let someone wiser and clearer answer this.</p>

<p>2) Yes and no? Allow me to explain and come to your own conclusion.</p>

<p>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'')</p>

<p>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')</p>

<p>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. </p>

CC BY-SA 3.0
2013-10-19T00:41:45.960Z
2013-10-19T00:41:45.960Z
Lan
<p>I am not sure about (i). </p>

<p>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.</p>

<p>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'$.</p>

<p>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. </p>

CC BY-SA 3.0
2013-10-19T08:22:27.520Z
2013-10-19T08:22:27.520Z
Akshay
<p>I am interested in the following questions and would be grateful if anyone could give me hints or point me to articles:</p>

<p>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$.</p>

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

<p>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) </p>

CC BY-SA 3.0
2013-10-19T00:29:41.720Z
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.)
zpavlinovic
CC BY-SA 3.0
2013-10-19T21:58:49.963Z
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?
David Richerby
CC BY-SA 3.0
2013-10-19T23:02:40.877Z
@DavidRicherby: I think that given a regular language, its regular sublanguages are r.e. (see my answer), but perhaps I'm missing something trivial.
Marzio De Biasi
<fl.formal-languages><automata-theory>
Questions about regular languages and their sublanguages
StefanH
# Questions about regular languages and their sublanguages

(Asked by: username_0 on 2013-10-18)

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)

**Tags:** fl.formal-languages, automata-theory

> **Comments:**
> **username_1**: 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.)  
> **username_2**: 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?  
> **username_3**: @DavidRicherby: I think that given a regular language, its regular sublanguages are r.e. (see my answer), but perhaps I'm missing something trivial.  

---

## 4 answers

### Answer by username_4 on 2013-10-19. Score: 7

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.


---

### Answer by username_3 on 2013-10-19. Score: 4

> 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.](http://dl.acm.org/citation.cfm?id=1438639)).
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.

> **Comments:**
> **username_2**: 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.  
> **username_3**: @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.  
> **username_2**: 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.  
> **username_3**: @DavidRicherby: if it is correct, why it doesn't answer point (1) of the question?  
> **username_2**: 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.)  
> **username_3**: @DavidRicherby: ok, but I don't understand what you mean with "it's essentially best-possible" ? Do you mean that it is a weak result ? (I included the PSPACE reference only for pedantry, but the important fact in the (trivial) proof is that inclusion is decidable for regular languages)  
> **username_2**: It felt weak because you've gone from "decidable in PSPACE" to "recursively enumerable". However, since the answer can be infinite, we can't hope for a "nice" answer like, "It's in double-exp-space".  

---

### Answer by username_5 on 2013-10-19. Score: 2

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.


---

### Answer by username_6 on 2013-10-19. Score: 1

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.


---

