Is a language regular

Question

Given a regular language $L$ (so there is an automaton $A$ which recognizes $L$), I need to determine whether $ L'$ is also regular, where $L'$ is given by $$ L' = \{ \alpha \in \Sigma^* \mid (\exists \beta \in \Sigma^*)[ |\alpha| = 2 |\beta| \wedge \alpha\beta \in L \}.$$ As far as I understand, I have to construct an automaton $A'$ that recognizes the language $L$.

I was thinking of making the automaton so it has two pointers, one pointing at the beginning states and one at the final states, and the automaton states are the cartesian product of the automaton states from $A$, and the left pointer is going to move 2 states to the right, and the right pointer 1 state to the left. Any suggestions?

Answer 1

(I think by pointers you mean the "pebbles" that are described in Kozen's Automata and Computability.)

The language $L'$ is regular.

You can prove that as follows: Consider the DFA $D_1 = (Q, \delta, F, q_0)$ for $L$. We will create another automata $D_2 = (Q \times Q \times Q \times \{0,1\}, \Delta_2, F_2, I)$.

$I = \{(q_0, q, q, 0) : q,q_0 \in Q\}$

$F = \{q, q_F, q, 0 : q_F \in F, q \in Q \}$

Let's first understand the intuition before defining the transition function $\Delta_2$:

• We are constructing two layers: all the transitions in the first layer will be to some state in the second layer, and all those in the second layer will be toward the first layer.
• On reading an alphabet when on a state of the form $(q_1, q_2,q_2, 0)$, the state in the first entry will change as per the transition function of $D_1$. The state in the second entry will also follow $D_1$, but it will be symbol agnostic, in the sense that it can change to any state irrespective of the symbol. The third entry will remain the same. (It is used to save the state at which we started the second pebble). The fourth entry will change from 0 to 1 which is equivalent to moving from one layer to another.
• When on a state of the form $(q_1, q_2,q, 1)$, all the transitions are $\epsilon$ transitions and move us back to $(q_1, q_2',q_2, 0)$ where $q_2'$ is a state which is reachable from the state $q_2$ in $D_1$.

So in this automata, we first non-deterministically choose a start state of the form $(q_0, q, q,0)$. The state $q$ is the state from which we are reading $\beta$, and from $q_0$ we are reading the actual input $\alpha$. As the automata reads the word, for each letter of $\alpha$, we non-deterministically choose two letters for $\beta$ and run the same automata from that state in the second component. If on reading $\alpha$ we end up in the state we started reading $\beta$ (which is chosen non-deterministically), and the second component reaches a final state in $D_1$, then it means that the $\exists \beta : \alpha \beta \in L$. And hence we accept.

Formally, \begin{equation} \Delta_2((q_1, q_2, q, 0),a) = \{(\delta_1(q_1, a), \delta(q_2, x), q, 1) : x \in \Sigma)\}\\ \Delta_2((q_1, q_2, q, 1),\epsilon) = \{(q_1, \delta(q_2, x), q, 0) : x \in \Sigma)\} \end{equation}.

---

There is an easier way (as OP described): Let $D_1'$ be the NFA obtained by reversing all the transitions in $D_1$ and allowing all symbols for each transitions (i.e., make it symbol agnostic). Take the states to be 3-tuples from $Q \times Q \times \{0,1\}$. Start from $(q_0, q_f, 0)$ where $q_f \in F$. On reading a letter, move from state $q_0$ as per $D_1$, and move two steps from $q_f$ according to the $D_1'$. The final states can be $(q,q,0)$ where $q\in Q$.

You can try figuring out why this works.

Answer 2

Take the language L and an DFA for it. For any two states $S_i$ and $S_j$, we can determine all the lengths of strings that would go from $S_i$ to $S_j$: To get there, we will have single character transitions, and loops, and in any case the possible lengths will be of the form ak + b for fixed a ≥ 1 and 0 ≤ b < a and k ≥ $k_0$, plus various lengths < $ak_0$. Then we calculate the lengths of all strings that lead from $S_i$ to an accepting state, they will have the same form. Then we calculate the lengths of strings that the input string reaching $S_i$ could have to be in L', these are twice the lengths of strings going from $S_i$ to an accepting state.

For example a*(bb)*c: After processing zero or more a's, k characters can lead to an accepting state, k ≥ 1. After processing an even number of b's, it is 2k+1, k ≥ 0. After an odd number of b's, it's 2k, k ≥ 1. After the c, it's 0. Anything else, it is empty. So the lengths of strings that may lead to these states are 2k, k ≥ 1, or 4k+2, k ≥ 0, or 4k, k ≥ 1, or 0, or none at all.

We now split the states of the DFA to keep track of the steps needed to get there. If the number of steps is right, the state is accepting.

We now modify the DFA: We split each