If you want to make money online : Register now

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

, ,
Problem Detail:

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}

#### Answered By : Yuval Filmus

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.

###### Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/35170

3200 people like this