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.

  • 1
    $\begingroup$ 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.) $\endgroup$
    – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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