# Automata for languages derived from an automaton by number of state visits

My question in response to this answer: what would the finite automata look like for $L_1$ and $L_0$ in the answer?

I get how the languages are formed; however, since $M_L$ cannot remember how many times it has looped, how does $q$ branch off (if it does) into the two different DFAs for $L_0$ and $L_1$?

Definitions:

• $L$ = infinite regular language

• $q$ = state within the DFA for $L$, $M_L$, where $M_L$ loops

• $L_1$ = {w in A | $q$ is visited an odd number of times}

• $L_0$ = {w in A | $q$ is visited an even number of times}

• it would be better to make the question somewhat self contained with some descr overview etc – vzn Jan 12 '15 at 15:56

## 1 Answer

Starting with an automaton for $L$ with state set $Q$, starting state $s_0$, transition function $\delta$, and accepting states $F$, here is how to construct automata $M_1,M_0$ for $L_1$ and $L_0$. The state set of both is $Q \times \{0,1\}$. The starting state is $(s_0,0)$. The transition function is given by $$\delta'((s,x),a) = \begin{cases} (\delta(s,a),x) & \text{ if } \delta(s,a) \neq q, \\ (\delta(s,a),1-x) & \text{ if } \delta(s,a) = q. \end{cases}$$ The accepting states of $M_1$ are $F \times \{1\}$, and of $M_0$ are $F \times \{0\}$.

In words, in addition to remember the original state, the new automaton also remembers the parity of the number of times that $q$ has been visited. Acceptance is determined accordingly.

• $s$ is within Q and x is either 0 or 1, correct? So, if I'm understanding this correctly, the transition functions for both $M_1$ and $M_2$ are as follows: the state $M_1$ and $M_2$ are in 'following' the string $a$ equals the pair of the state when $L$ starts from state $s$ and reads in string $a$ and $x$ if $L$'s final state starting from state $s$ and reading in string $a$ is equal to $q$ (and similarly for the second part)? – tdark Dec 12 '14 at 2:17
• No, this description is wrong. The second part $x$ counts the number of times that $q$ has been visited, modulo 2. – Yuval Filmus Dec 12 '14 at 2:19
• Oh! So this delta-hat is for $M_L$, and the two conditions represent the delta functions for $M_1$ and $M_0$, respectively? – tdark Dec 12 '14 at 2:23
• I don't know what delta-hat is (presumably $\delta'$, read delta prime), nor what two conditions you refer to. If you refer to the two condition son the displayed equation defining $\delta'$, then no, the definition is exactly the same for $M_1$ and for $M_0$, and the two cases correspond to visiting $q$ (second case) and visiting any other state (first case). At this point I suggest you take a couple of hours to try and understand the construction on your own. – Yuval Filmus Dec 12 '14 at 2:27
• Ok I think I understand now. For the second half of the delta prime equation, it is $1-x$ because we are visiting $q$ again by following $a$, which means the number of times we visited $q$ increased by one, which when we take that mod 2 gives us the opposite of what $x$ was previously, correct? – tdark Dec 12 '14 at 2:53