2
$\begingroup$

If I have the following two languages:

$L_1= \{ w \in \{a,b\} |$ $w$ has neither $ab$ nor $ba$ as a subword$\}$

$L_2= \{ w \in \{a,b\}^* |$ $w$ has neither $ab$ nor $ba$ as a subword$\}$.

Is there any difference between $L_1$ and $L_2$? I understand the impact of the Kleene star, but I don't see what difference it makes here.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Yes there is. $w \in \{ a, b\}$ means that $w$ may be either $a$ or $b$, while $w \in \{ a, b\}^*$ means that $w$ may be a string over $a$ and $b$ including the empty string $\epsilon$. In particular $L_1$ is a language having only $a$ and $b$, i.e, $L_1 = \{a, b\}$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So for $L_1$ is ab not even a possible word? $\endgroup$
    – user79878
    Commented Jan 1, 2018 at 14:08
  • 1
    $\begingroup$ Yes, you are right. $\endgroup$
    – fade2black
    Commented Jan 1, 2018 at 14:09

Your Answer

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