0
$\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.

$\endgroup$
  • $\begingroup$ Let $R$ be a regular expression. $\epsilon \in L( R^*)$ $\endgroup$ – abc Apr 2 '17 at 13:08
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^+$

| cite | improve this answer | |
$\endgroup$
  • $\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 '17 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 '17 at 13:52
  • $\begingroup$ @RickDecker Thank you I understand now! Also thanks for newbie $\endgroup$ – YOUSEFY Apr 3 '17 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.

| cite | improve this answer | |
$\endgroup$
  • $\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 '17 at 8:08

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.