3
$\begingroup$

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}

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

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.

$\endgroup$
  • $\begingroup$ $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)? $\endgroup$ – tdark Dec 12 '14 at 2:17
  • $\begingroup$ No, this description is wrong. The second part $x$ counts the number of times that $q$ has been visited, modulo 2. $\endgroup$ – Yuval Filmus Dec 12 '14 at 2:19
  • $\begingroup$ Oh! So this delta-hat is for $M_L$, and the two conditions represent the delta functions for $M_1$ and $M_0$, respectively? $\endgroup$ – tdark Dec 12 '14 at 2:23
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 12 '14 at 2:27
  • $\begingroup$ 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? $\endgroup$ – tdark Dec 12 '14 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.