Are the regular languages closed against injecting single letters?

Question

Let $L$ an arbitrary regular language and

$\qquad L_2 = \{uav : uv \in L\}$.

Am I correct to say that this language is not regular by saying:

$L$ has an even number of $a$'s. So $u$ and $v$ have an even number of $a$'s. However, $uav$ will have an odd number of $a$'s so $L_2$ is not regular?

Answer 1

General approach if one wants to show that an operation on languages preserves regularity is to assume that the language $L$ is regular, and given as automaton/ expression/ grammar. Based on this representation build a new automaton/ expression/ grammar, and explain the new construct actually represents $L_2$.

For instance, we can do so using regular expressions. See the answer *Showing Regular Languages are closed under removal of rightmost character for a related solution.

Let $\iota$ be the operator that inserts a single occurrence of the symbol $a$ into a language. We can transform a regular expression for $L$ into a regular expression for $L_2$ by defining recursively

• $\iota(\varnothing) = \varnothing$
• $\iota(\varepsilon) = a$
• $\iota(\sigma) = a\sigma + \sigma a$
• $\iota(RS) = \iota(R)S + R\iota(S)$
• $\iota(R+S) = \iota(R) + \iota(S)$
• $\iota(R^*) = R^*\;\iota(R) \;R^* + a$

Alternatively, here is a proof using closure properties. We know that the regular languages are closed under intersection (with regular languages) and under morphisms and inverse morphsims.

Let $c$ be a new symbol. Let $\varphi: \{a,b,c\}^* \to \{a,b\}^*$ be the morphism that deletes copies of $c$. Thus $\varphi^{-1}$ is the mapping that inserts copies of $c$ at arbitrary positions. Let $\psi: \{a,b,c\}^* \to \{a,b\}^*$ be the morphism that maps $a,c$ to $a$ and $b$ to $b$ (so it only changes the occurrences of $c$ into $a$. Finally let $K$ be the language over $\{a,b,c\}$ of all strings that contain exactly one occurrence of $c$.

Then $L_2 = \psi(\varphi^{-1}(L)\cap M)$, and is regular whenever $L$ is regular. $\varphi^{-1}$ chooses the position of the extra $a$, $M$ verifies exactly one position was selected, and $\psi$ puts $a$ at the selected position.

Answer 2

This language is regular. Let $M$ be a DFA accepting $L$ and assume it has a single initial and final state. We can construct a NFA accepting $L_2$. We create two copies of $M$: $M_1$ and $M_2$. Let us denote the states of $M_1$ as $q_1, \dots, q_n$ and the states of $M_2$ as $p_1, \dots, p_n$. Note that these two DFA are isomorphic where $q_i$ corresponds to $p_i$. The initial state of the new automaton will be $q_1$, and its accepting state will be the accepting state of $M_2$ (so the accept state of $M_1$ is no longer an accept state, and the initial state of $M_2$ is no longer an initial state; in the new NFA, these are just normal states). Add new transitions $\delta(q_i, a) = p_i$ for each pair $(q_i,p_i)$. The resulting NFA accepts $L_2$. You can think over it to prove it accepts $L_2$; effectively, $M_1$ is reading the $u$ part of the input and $M_2$ is reading the $v$ part.