Let's say you have a set of strings $R$. A string $s$ is part of my language $S$ iff there is a string $r \in R$ such that $s$ is an initial segment of $r$ (you can get $s$ by removing characters from the end of $r$). For example, if $R=\{``Hi",``Sir",``"\}$, then $S=\{``", ``H", ``Hi", ``S", ``Si", ``Sir"\}$. My question is, if $R$ is a regular language, is $S$ necessarily a regular language?
If not, provide a counterexample. (Also, if it is true, a constructive proof would be best; I plan on making an algorithm to regular expressions into regular expressions for partial matching.)
Start with a DFA $M$ for $R$. To get a DFA $M'$ for $S$, you need only modify the set of acceptor states. Specifically, if $q$ is a state of $M$, make it an acceptor state for$M'$ if it's an acceptor state of $M$ or there is a path from it to an acceptor state of $M$.