1
$\begingroup$

\begin{align} L &= \{ w \in \{a, b\}^* \mid \text{ no prefix of $w$ starts with $b$}\} \\ &= \{w \in \{a, b\}^* \mid \text{ the first character of $w$ is $a$} \} \cup \{e\} \end{align}

Why is it in union with an empty string? If an empty string from $b$ can also be a prefix.

$\endgroup$
3
$\begingroup$

The unique prefix of the empty word $e$ is $e$, and it does not start with $b$. Therefore $e$ satisfies the condition "no prefix of $e$ starts with $b$" and hence $e$ belongs to $L$.

$\endgroup$
2
  • $\begingroup$ "L3= {w E {a I b} * : every prefix of w starts with b} = null set. L3 is equal to 0 because e is a prefix of every string. Since e does not start with b, no strings meet L3's requirement." That is according to the book I am using. I am confused. $\endgroup$
    – log
    Sep 27 '19 at 13:43
  • $\begingroup$ Take any word $w$. Then $e$ is a prefix of $w$, right? And $e$ does not start with $b$, right? Thus it is not true that every prefix of $w$ starts with $b$, since you just found one prefix, namely $e$, that does not start with $b$. Thus no word $w$ satisfies the condition defining $L_3$ and hence $L_3$ is the empty language. $\endgroup$
    – J.-E. Pin
    Sep 27 '19 at 16:50

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.