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$
  • $\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$ – Shreesh Jun 12 '18 at 8:47
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, privacy policy and cookie policy

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