3

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?

Asaf Karagila
  • 393,674
Anonymous User
  • 145

2 Answers2

3

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.

Numbra
  • 995
  • 4
  • 10
3

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)$.

Brian M. Scott
  • 616,228