# Languages accepted by modified versions of finite automata

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.

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.

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.

• Very nice to spot that counter example for type-2! – Dave Clarke Mar 14 '12 at 16:53
• @Dave Clarke: thanks. It's a bit of a silly example, but it works :) – Alex ten Brink Mar 14 '12 at 16:55
• "Pathological" in place of "silly". – Dave Clarke Mar 14 '12 at 16:56
• 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. – Patrick87 Mar 14 '12 at 16:57
• 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? – Patrick87 Mar 14 '12 at 16:59