Regular language minus one word from it is regular

665 Views Asked by At

I can't find this proposition anywhere, so I started doubting if it is true.
Is my proof incorrect, or is the proposition true, just not important enough to be mentioned?

Proposition:
Let $\Sigma$ be an alphabet, $L$ a regular language, and $w\in L$. Then $L\setminus \{w\}$ is regular.

Proof:
Using

  1. Complement of a regular language is regular.
  2. The language $\{w\}$ is regular.
  3. Union of two regular languages is regular.

we deduce that $\left(\Sigma^\star\setminus L\right)\cup\{w\}$ is also regular. Then, so is its complement: $$\begin{align}\Sigma^\star\setminus\left(\left(\Sigma^\star\setminus L\right)\cup\{w\}\right)&=\left(\Sigma^\star\setminus\left(\Sigma^\star\setminus L\right)\right)\setminus\{w\} \\ &= L\setminus\{w\} \end{align}$$ Therefore, we have proven that $L\setminus\{w\}$ is regular. $\blacksquare$

1

There are 1 best solutions below

0
On BEST ANSWER

You are correct. You can even make this sort of more general statement: if $L_1$ and $L_2$ are regular, then $L_1\setminus L_2$ is regular. This is proved just like you did in the case $L_2=\{w\}$, the only thing used about $L_2$ is that it's regular.