Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 1 down vote accepted

HINT: Start with a DFA $M$ that recognizes $L$. Let $Q$ be the set of states of $M$, and let $s_0$ be the initial state. For each $w\in L$ let $Q(w)$ be the set of states through which $M$ passes when reading $w$, and let $Q_0=\bigcup\{Q(w):w\in L\}$; every state in $Q_0$ is the initial state for some word in $P$, so add an $\epsilon$-transition from $s_0$ to each $q\in Q_0$. Call the new automaton $M_1$; $$L(M_1)=\{v\in A^*:uv\in L\text{ for some }u\in A^*\}\;.$$

This does half the job.

Now suppose that $q\in Q(w)$ for some $w\in L$; then there is some $v\in A^*$ that takes $M$ from $q$ to an acceptor state. If $u\in A^*$ is any word that takes $M$ from $s_0$ to $q$, $uv\in L$. Modify $M$ by making each state in $Q_0$ an acceptor state, and call the resulting automaton $M_2$; $$L(M_2)=\{u\in A^*:uv\in L\text{ for some }v\in A^*\}\;.$$

Now just combine the ideas.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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