If you want to make money online : Register now

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

, , No Comments
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$?


  • $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}

Asked By : tdark

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

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback