patternMinor
Automata for languages derived from an automaton by number of state visits
Viewed 0 times
fromnumberlanguagesautomataforstatevisitsderivedautomaton
Problem
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}
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}
Solution
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.
$$
\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.
Context
StackExchange Computer Science Q#35170, answer score: 2
Revisions (0)
No revisions yet.