If L is regular, so is $L-\{λ\}$?

Question

A language is regular, by definition, if you can create a DFA for it. Then I need to prove that if $L$ is regular, then so is $L-\{\lambda\}$ for any $\lambda\in L$. Any ideas?

Answer 1

There are several ways of proving a language is regular. One, which by the wording of your question suggests was your first attempt, is to construct an explicit DFA which recognizes your language. In your problem, such an explicit construction is impossible since you do know the shape of the DFA that recognizes the original language $L$. Nevertheless, you could try to describe a procedure for taking a DFA for $L$ and explicitly describing how to modify the DFA to recognize $L-\{\lambda\}$. This would probably require a pretty intricate construction.

Alternatively, and much less painfully, is to use closure properties of regular languages. For example, the set of regular languages is closed under intersection and complements, and hence under set difference (why?). Since $\{\lambda\}$ is regular (why?) and $L$ is regular, so must be $L-\{\lambda\}$. Note that this latter approach is basically the same as the first approach, but sweeping all the messy DFA constructions into the proofs of the closure properties.

Answer 2

Here's the (sort of) proof using only DFA.

• if $\lambda \notin L$, then $L = L - \{\lambda\}$, so the same DFA accepts $L - \{\lambda\}$.
• If $\lambda \in L$, then the initial state must be a final state ($q_0 \in F$). However, we cannot just make it non-final since there might be some transition leading to the state, as the image: To get around this, we create a new non-final initial state $p_0$ that no transition leads into, and for every $\delta(q_0, i) = q_j$ we add an extra transition $\delta(p_0, j) = q_i$: This way, we are able to accept all other strings that requires going back to the state $q_0$ but reject $\lambda$, Proving that we can construct a DFA for $L - \{\lambda\}$ if $L$ is regular.

Answer 3

Another option here is to obtain a regular expression for $L$, then transform it into a regex for $L - \{\lambda\}$. To do so, let’s define a function $D(R)$ (for “delambda”) that takes in a regex $R$ and outputs a regex for the language of $R$, except that $\lambda$ has been removed. We’ll do it inductively over the regexes:

• $D(\emptyset) = \emptyset$. (The empty set already doesn’t match $\lambda$)
• $D(\lambda) = \emptyset$. (If the regex only matches $\lambda$, now it doesn’t match anything.)
• $D(\mathtt{a}) = \mathtt{a}$ for all $\mathtt{a} \in \Sigma$. (Any single character already doesn’t match $\lambda$).
• $D(R_1 \cup R_2) = D(R_1) \cup D(R_2)$. (To match a nonempty string that matches either $R_1$ or $R_2$, match either a nonempty string that matches $R_1$ or a nonempty string that matches $R_2$.)
• $D(R_1 R_2) = D(R_1) R_2 \cup R_1 D(R_2)$. (To match a nonempty string made by gluing a string matching $R_1$ and a string matching $R_2$, at least one of the two strings matched must be nonempty.)
• $D(R^\ast) = R^\ast D(R).$ (A nonempty string formed by gluing together many strings matching $R$ must have at least one of the strings glued together nonempty.)

Applying this transform to any regex will produce one for the same language but without the empty string.