# Proof that $A^* - \{x\} = A^+$ such that $A=\{a,b\}$ and $x \in \{a,b\}^*$

Exercise 1.1 (2) from Problem Solving in Automata, Languages, and Complexity by Du and Ko. P.7. the question is as following:

Let A be a langauge over {a,b} and $x \in {a,b}^*$. Find necessary and sufficient conditions in terms of x and A for the equation: $$A^* - \{x\} = A^+$$

thus, by substation: $$\{a,b\}^* - \{\{a,b\}^*\} = \{a,b\}^+$$

Now this the LHS should equal to $\{a,b\}^*$ because if we have two sets A and B, then $A \cap B = \phi$, then $A-B=A$. Now where is wrong?!!

I'm also trying to prove from RHS since this is equality to proof should be from both direction.

• Let $R$ be a regular expression. $\epsilon \in L( R^*)$ – abc Apr 2 '17 at 13:08

Consider the regular expression $(a+b)^*$ as an example.

$(a+b)^+=(a+b)\cdot(a+b)^*$

In $(a+b)^+$,with respect to $(a+b)^*$, you are forbidding the generation of the empty string, that is you are removing $\epsilon$.

This could be generalized to every language $A$, either in the case of $A$ empty.

In fact if $A=\emptyset$:

• $A^*=\emptyset^*=\{\epsilon\}$
• $A^+ =\emptyset \cdot \emptyset^*=\emptyset$

and $A^* \setminus \epsilon = A^+$

• Thank you for your answer. if $x \in \epsilon$ then clearly $A^* - \{ \epsilon \} = A^+$ since $A^* \cap \{ \epsilon \} = \{ \epsilon \}$. Now, the second case: if $x \notin \{ \epsilon \}$ then we have something like $A^* - \{ababaa ..\} = A^*$ since $\epsilon$ is not removing from the second! Is that right? – YOUSEFY Apr 3 '17 at 8:03
• @YOUSEFY. $x\notin\{\epsilon\}$ is equivalent to saying $x\ne\epsilon$. In that case $A^*\setminus\{x\}$ will be all possible concatenations of strings in $A$, with the single exception that $x$ won't be there, just as $A^*\setminus\{\epsilon\}$ will be all of $A^*$ except for the empty string. – Rick Decker Apr 3 '17 at 13:52
• @RickDecker Thank you I understand now! Also thanks for newbie – YOUSEFY Apr 3 '17 at 17:49

Your problem is that in going from $A^*-\{x\}$ to $\{a,b\}^*-\{\{a, b\}^*\}$ you went a step too far. In the first expression, $x$ is a single string over the alphabet. Replacing that with the general expression $\{\{a,b\}^*\}$ is incorrect, if for no other reason that $\{\{a,b\}^*\}$ is a set consisting of a set of words and not a single word.

• Thank you for your point. Suppose the following: A - x, where $x \in A$, then we know that $A - x$ is the same as all A except x. so single string is only effecting if there is intersection between set A and if there is no such intersection, then A-x=A? Is there wrong with my argument! – YOUSEFY Apr 3 '17 at 8:08