|
I need some help with the following problem: $L$ - regular language and i have to prove that the language $P$ = {$\alpha$| $\beta\alpha\gamma \in L$, $\beta,\gamma \in (A)^*$} is regular. In other words $P$ is the language of all parts of words from $L$. Thanks a lot! |
||||
|
|
|
Lazy solution, by using other closure properties. Middles are actually substrings. They are obtained by taking suffixes of prefixes of the original language. Both operations of taking prefixes and taking suffixes applied to regular languages will result in regular languages. |
|||
|
|
|
$L$ is a regular language, so you have a DFA $M$ for it. First remove every “dead” state in $M$, i.e. every state that cannot lead to an accepting state. Make every state in $M$ an accepting state, and make a new start state that $\epsilon$-branches to every state in $M$. The resulting NFA $M'$ recognizes $P$, because: a) If the string $bac$ was accepted by $M$, then there was a sequence from $Start$ through $S1$ that recognizes $b$, a sequence from $S1$ to $S2$ that recognizes $a$, and a sequence from $S2$ to an accepting state $S3$ that recognizes $c$. But $S1$ is now connected to $Start'$ through $\epsilon$-transitions and $S2$ is an accepting state, hence $M'$ accepts $a$. b) Conversely, because we have removed transitions that cannot lead to an accepting state, every sequence recognized by $M'$ was part of an accepting sequence for $M$. Because we have not added any edges except those that can be used only to skip $b$, this sequence was consecutive in $M$. Something like that, not very rigid, may be wrong, but I am in a haste. |
|||
|
|
