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}

Improve this question
$\endgroup$
1
  • $\begingroup$ it would be better to make the question somewhat self contained with some descr overview etc $\endgroup$
    – vzn
    Commented Jan 12, 2015 at 15:56

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\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
    Commented Dec 12, 2014 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
    Commented Dec 12, 2014 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
    Commented Dec 12, 2014 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
    Commented Dec 12, 2014 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
    Commented Dec 12, 2014 at 2:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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