1
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ Let $R$ be a regular expression. $\epsilon \in L( R^*)$ $\endgroup$
    – abc
    Apr 2, 2017 at 13:08

2 Answers 2

Reset to default
2
$\begingroup$

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^+$

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – YOUSEFY
    Apr 3, 2017 at 8:03
  • 1
    $\begingroup$ @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. $\endgroup$
    – Rick Decker
    Apr 3, 2017 at 13:52
  • $\begingroup$ @RickDecker Thank you I understand now! Also thanks for newbie $\endgroup$
    – YOUSEFY
    Apr 3, 2017 at 17:49
2
$\begingroup$

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.

To complete this answer, see newbie's comment on your original post.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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! $\endgroup$
    – YOUSEFY
    Apr 3, 2017 at 8:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.