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.

$\endgroup$
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\}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy