Proving prefix/suffix exists for finite automata My task is to show that if a language $L \subseteq \{a, b\}^*$ is recognised by a finite automaton then there exists a finite automaton that recognise all the prefixes and suffixes of the word in $L$.
$$\text{Pref}(L) = \big\{x \in \{a,b\}^* \big| xy \in L\text{ for some }y \in \{a,b\}^*\big\}$$
and
$$\text{Suff}(L) = \big\{y \in \{a,b\}^* \big| xy \in L\text{ for some }x \in \{a,b\}^*\big\}$$
I've come so far to understand that:
A word $u$ is a prefix of a word $v$ if there is a word $w$ such that $v=uw$.
And intuitively I somehow believe that for a word $w$ a prefix/suffix can be all the partitions(?) in order for the word $w$, for example if the word is $abab$ then the possible prefixes/suffixes are
$$\big\{\emptyset, \{a\}, \{ab\}, \{aba\}, \{abab\}\big\}$$
However, I'm having a hard time actually proving this in a mathematical way. What I assume is that for a given finite automata, we'd have to turn all the states on a path to an accepting state into accepting states? Anyone care to help me prove these two?
 A: There are many ways to prove these kind of statements, but I think that it is useful to remember that a language $L \subseteq \{a, b\}^\ast$ can be recognized by a finite-state automaton if and only if it can be described as a regular expression.
We can then proceed by induction on the structure of regular expressions:

*

*If $L$ is empty, $L = \{\varepsilon\}$ or $L = \{x\}$ for some $x \in \{a, b\}$ then result is trivial.

*If L = $L_1.L_2$ (concatenation) then $Pref(L) = Pref(L_1) \cup L_1.Pref(L_2)$, both of which are regular languages by induction, and so their union is also a regular language.

*If $L = L_1^\ast$ then ...

*If $L = L_1|L_2$ then ...

In general, using a different characterization of regular languages gives another point-of-view, leading to some easier, clearer or more elegant proofs.
A: SKETCH: You have the right idea for half of the problem. Suppose that $M$ is a DFA for $L$. You can modify $M$ to get a DFA $M_P$ for $\operatorname{Pref}(L)$ by letting $S_0$ be the set of all states of $M$ from which an acceptor state of $M$ can be reached, including the acceptor states of $M$ themselves, and making $S_0$ the set of acceptor states of $M_P$. No other changes are needed.
You can modify $M$ to get an NFA $M_S$ for $\operatorname{Suff}(L)$ in either of two ways: if $S_1$ is the set of states of $M$ that are accessible from the initial state of $M$, you can either make all of the states in $S_1$ initial states of $M_S$, or add $\epsilon$-transitions from the initial state of $M$ to each state in $S_1$.
Now use a standard construction to combine $M_P$ and $M_S$ to get an NFA for $\operatorname{Pref}(L)\cup\operatorname{Suff}(L)$.
