Prove that the class of regular languages is closed under three operation

We define an operation three on strings as three(c1c2c3c4c5c6...) = c3c6... then the above-described definition is extended to languages. Prove that the class of regular languages is closed under this operation.

• If $R$ is regular, there is a DFA which recognises it. Given a DFA $D$, how can you make a finite automaton which recognises $\mathit{three}(L(D))$? ($D$ doesn't really have to be deterministic. But it might help your thinking.)
– rici
Oct 24 '21 at 3:37

Let $$Q$$ be a $$DFA$$ recognizing $$L$$. To show that $$\mathrm{three}(L)$$ is regular, you only need to construct a $$NFA$$ deciding $$\mathrm{three}(L)$$ (this suffices, since any $$NFA$$ can be transformed to an equivalent $$DFA$$). Now, the key idea is that if the $$NFA$$ is reading, say, the first character $$c_3$$, then it can guess what two characters $$c_1,c_2$$ occurred before it.

More formally, suppose that $$Q = (\Sigma,S,s_0,\delta,F)$$. Given a string $$\overline{x} \in \Sigma^*$$ and states $$s,s' \in S$$ we will use $$s,\overline{x} \to s'$$ to denote the fact that $$Q$$, starting from state $$s$$ while reading the first character of $$\overline{x}$$, ends up in state $$s'$$ after reading the entire string $$\overline{x}$$. Consider now the following non-deterministic finite automata $$Q' = (\Sigma,S\cup \{s_0'\},s_0',\delta',F)$$, where $$s_0' \notin S$$ and the transition function $$\delta$$ is defined as follows:

• For every $$s\in S$$ and $$z\in \Sigma$$ we define $$\delta(s,z) := \{s' \in S \mid \exists x,y \in \Sigma : s,xyz \to s'\}$$
• For every $$z\in \Sigma$$ we define $$\delta(s_0',z) := \{s'\in S \mid \exists x,y \in \Sigma:s_0,xyz \to s'\}$$

It is straightforward to verify that $$L(Q') = \mathrm{three}(L)$$.

You might use closure properties of the regular languages: (inverse) homomorphisms and intersection (by regular languages).

Assuming the language is over the alphabet $$\Sigma$$, make two copies $$\Sigma_i = \{ \sigma_i\mid \sigma\in\Sigma \}$$ of that alphabet, $$i=0,1$$.

The homomorfism $$h$$ maps elements from $$\Sigma_0\cup\Sigma_1$$ onto their original $$h:\sigma_i\mapsto\sigma$$. The inverse morphism $$h^{-1}: \Sigma^* \to (\Sigma_0\cup\Sigma_1)^*$$ nondeterministically chooses a $$0$$ or $$1$$ copy for each symbol.

Now let $$g$$ be the homomorfism on $$\Sigma_0\cup\Sigma_1$$ that deletes symbols from $$\Sigma_0$$ and maps symbols from $$\Sigma_1$$ onto their original.

Now the following composition keeps every third symbol, while deleting the other symbols $$w\mapsto g(\;h^{-1}(w) \cap (\Sigma_0\Sigma_0\Sigma_1)^*(\Sigma_0^0\cup\Sigma_0^1\cup\Sigma_0^2)\;)$$.

This method has the advantage that it also works for context-free languages.