My proof was deemed false because it does not work for infinite regular languages, but I don't understand why.

Prove: "If we remove one string from any nonempty regular set, the resulting set is still regular.

I used to lemmas:

  • A set containing only one string is trivially a regular language
  • The union operator is closed in the class of regular languages

Given these two lemmas, I made the claim that any regular language $L$ can be written in the form $$L = \bigcup_{e \in L}\{e\}$$

Then, one picks an arbitrary string $r \in L$ to remove, and expresses $L$ in the same manner with $r$ distinct: $$L = \bigcup_{e \in (L - \{r\})}\{e\} \cup \{r\}, \quad r \in L$$

Finally, we simply remove $r$ from the union and obtain: $$L' = \bigcup_{e \in (L - \{r\})}\{e\}$$

$L'$ is also regular by the two lemmas introduced earlier.

  • $\begingroup$ You implicitly use the proposition "if A and B are regular languages, and $A=B\cup C$, then C is a regular language". This is different from the proposition "the union operator is closed in the class of regular languages". $\endgroup$
    – xskxzr
    Feb 1 '18 at 8:34
  • $\begingroup$ "My proof was deemed false because it does not work for infinite regular languages" -- this doesn't seem to be helpful critique. Your proof does not work at all; it has nothing to do with whether $L$ is finite. $\endgroup$
    – Raphael
    Feb 1 '18 at 9:21

The problem with your argument is in the interpretation of the second lemma. Closure under union says "If $L_1$ and $L_2$ are regular languages, then $L_1\cup L_2$ is regular." By induction, then, the union of any finite collection of regular languages is regular. You cannot, however, conclude that the union of an arbitrary collection of regular languages is regular, as Raphael pointed out, since your observation $$ L=\bigcup_{e\,\in\, L}\{e\} $$ is true for any language at all, regular or not, so since a single string language is regular, then every language would be regular.

What you could do is exploit some other closure properties of regular languages. For instance

  1. If $L_1$ and $L_2$ are regular languages, so is $L_1\cap L_2$.
  2. If $L$ is a regular language, its complement $\overline{L}$ is too.
  3. We can thus write the set difference $A\setminus B$ as $A\cap\overline{B}$ so regular languages are closed under set difference.
  4. If $L$ is any regular language and $e\in L$ is any string in $L$, then $L\setminus \{e\}$ must also be regular.

The problem is that you don't actually show anything.

Every language can be expressed as union of singletons. So being able to write down $L'$ as such does not show it's regular. For all we know, it may not even be recursively enumerable.


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.