16
$\begingroup$

A deterministic finite automaton (DFA) is a state machine model capable of accepting all and only regular languages. DFAs can be (and usually are) defined in such a way that each state must provide some transition for all elements of the input alphabet; in other words, the transition function $\delta : Q \times \Sigma \rightarrow Q$ should be a (total) function.

Imagine what we will call a doubly deterministic finite automaton (DDFA). It is defined similarly to a DFA, with two exceptions: first, instead of the transition leading from one state to one other state for every possible input symbol, it must lead to two distinct states; second, in order to accept a string, all potential paths must satisfy either one or the other of the following conditions:

  1. All potential paths through the DDFA lead to an accepting state (we will call this a type-1 DDFA).
  2. All potential paths through the DDFA lead to the same accepting state (we will call this a type-2 DDFA).

Now for my question:

What languages do type-1 and type-2 DDFAs accept? Specifically, is it the case that $L(DFA) \subsetneq L(DDFA)$, $L(DDFA) = L(DFA)$, or $L(DDFA) \subsetneq L(DFA)$? In the case that $L(DDFA) \neq L(DFA)$, is there an easy description of $L(DDFA)$?

Proofs (or at least moderately fleshed-out sketches) are appreciated, if they aren't too complicated.

$\endgroup$

2 Answers 2

9
$\begingroup$

This combined with Alex's answer give the complete picture.

$L(DDFA)\subseteq L(DFA)$ can be proven by adapting the usual powerset construction with a modified final state condition. In the power set construction, states are sets of states from the original automaton. Usually after performing the powerset construction, a state is final if one of the states in the set is final in the original automaton.

  • In type-1 DDFA, final states in the constructed automaton are the sets where all elements are final in the original automaton.

  • In type-2 DDFA, final states are the singleton sets of the final states from the original automaton.

In both cases, the resulting automata are DFAs.

Now type-2DDFA's can express only the languages $\{\epsilon\}$ and $\emptyset$, depending on whether the starting state is accepting or not. This is because the two transitions from a state need to go to distinct states, but acceptance is only possible if they end up on the same state.

$\endgroup$
7
$\begingroup$

To start off the analysis, I can say that $L(DFA) \subseteq L(DDFA)$ for type-1.

You can do this by duplicating a DFA and adding edges to duplicated states. If a state $s_1$ has a transition to $s_2$ on $x$, you make a transition from $s_1$ to $s_2'$ on $x$ as well. In addition, $s_1'$ has a transition to $s_2$ and $s_2'$ on $x$. Obviously, this means we will nearly always be in states $s_i$ and $s_i'$ at the same time (or possibly only $s_i$, initially), and hence we will recognize the same language.

Update: we also have $L(DFA) \neq L(DDFA)$ for type-2, as there does not exist a type-2 DDFA that recognizes the language $\{ a \}$. If you try to make such a DDFA, you have a start state $s$, and then you have to have two outgoing edges to states $s_1$ and $s_2$ on an $a$, but these states must be distinct, and hence the two accepting paths end in different accepting states.

Together with Dave Clarke's answer, that gives you the complete analysis.

$\endgroup$
8
  • 1
    $\begingroup$ Very nice to spot that counter example for type-2! $\endgroup$ Mar 14, 2012 at 16:53
  • $\begingroup$ @Dave Clarke: thanks. It's a bit of a silly example, but it works :) $\endgroup$ Mar 14, 2012 at 16:55
  • $\begingroup$ "Pathological" in place of "silly". $\endgroup$ Mar 14, 2012 at 16:56
  • $\begingroup$ Very nice job, guys. There were four things to check, and each of you got two. Unless either of you objects, I'll select @DaveClarke 's as the answer, only because he has less rep than Alex. $\endgroup$
    – Patrick87
    Mar 14, 2012 at 16:57
  • 1
    $\begingroup$ On a related note, would you like to elaborate on the languages accepted by type-2 DDFAs, or should I ask a separate question and link to this one? $\endgroup$
    – Patrick87
    Mar 14, 2012 at 16:59

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.