1
$\begingroup$

Let $L$ be a regular language, and $Pre(L)$ be the set of all words that are prefix of some word in $L$. Prove that $Pre(L)$ is regular.

My proof:

Let $M = (\Sigma, Q, \delta, q_0, F)$ be an automata such that $\mathcal{L}(M) = L$ and $Q' = \{ q \in Q \ | \ (\exists q_f, w \ | \ q_f \in F \ \wedge \ w \in \Sigma^{*}: [q, w] \mapsto^{*} [q_f, \lambda] ) \}$, that is, $Q'$ is the set of all states that have a path to a final state of $M$.

Hence, $M' = (\Sigma, Q', \delta, q_0, Q')$ is an automata such that $\mathcal{L}(M') = Pre(L)$. QED.

Is the last step right or should I now proof that the semantic of $M'$ is in fact $Pre(L)$?

$\endgroup$
1
  • $\begingroup$ It will help if you prove $ \mathcal{L}(M') = Pre(L)$. In other words: $ \mathcal{L}(M') \subseteq Pre(L)$ and $Pre(L) \subseteq \mathcal{L}(M')$ $\endgroup$ Jun 12, 2018 at 8:47

1 Answer 1

1
$\begingroup$

If you are unsure whether it is right, yes, you should prove it! This is a good general principle. If you are unsure whether or why a particular step is correct, there's a good chance a reader will be unsure, too -- so prove it in more detail until there is no doubt.

$\endgroup$

Your Answer

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

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