[Solved]: Languages accepted by modified versions of finite automata

ignougroup
Problem Detail: 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.

Asked By : Patrick87

Answered By : Dave Clarke

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/374  Ask a Question  Download Related Notes/Documents