This question already has an answer here:

Say $L \subseteq \{a,b\}^*$ is a regular language with words whose length is divisible by 3. Each word $w \in L$ has the form $w=xyz$ with $|x|=|y|=|z|$, where $y$ is then called the middle third of $w$.

I want to show that the language

$$L^{'}=\{y \in \{a,b\}^*:y \text{ is the middle third of a word } w \in L\}$$

is regular.

I could think of a description of language $L$ with the regular expression $((a+b)(a+b)(a+b))^*$. Would this be correct?

Unfortunately, I have no idea how to start to show that $L^{'}$ is regular. Could you please give me some hints to get started? I'd like to know how to solve this problem using an automaton, e.g. a NFA.

Thank you very much in advance.


marked as duplicate by J.-E. Pin, Alice Ryhl, hardmath, Cyclohexanol., Chappers May 13 '15 at 3:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ @J.-E.Pin I edited the question. I'd like to know how I can solve this problem using an automaton. I'm not very familiar with the concepts you used in your answer in the linked question. $\endgroup$ – Javiator May 12 '15 at 15:22
  • $\begingroup$ You can also look at this answer. $\endgroup$ – J.-E. Pin May 12 '15 at 15:57