HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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}

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.

Context

StackExchange Computer Science Q#35170, answer score: 2

Revisions (0)

No revisions yet.