2
$\begingroup$

I believe that I have a procedure for doing this, but I don't know how to approach the proof (and for that matter I'm not entirely sure the procedure is correct).

Here's the exact problem statement:

Given DFA $A = (\Sigma, Q, q_0, F, \delta)$ construct DFA $B$ from $A$ s.t. it accepts all words of the language of $A$ which have length distinct from 1.

And here's pseudocode that has to solve the problem followed by some explanation:

def ensure_word_length_ne_one(alphabet,
                              states,
                              initial,
                              final,
                              transition_function)
 loops = [i for i in alphabet if transition_function(initial, i) == initial)]
 new = make_new_accepting_state()
 # all arcs to the states directly accessible from the initial state
 # except the arcs from the initial state
 backarcs = [(arc.source, arc.destination, arc.input)
             for arc in arcs_to(set(for arc in arcs_from(initial))) -
                                set(arcs_from(initial))]
 for input in loops:
   # Remove all loops from the first state
   add_transition(initial, new, input)
   remove_transition(initial, initial, input)
   add_transition(new, new, input)
 for input in alphabet:
   # Bounce back from the new state to the first state
   add_transition(new, initial, input)
 for source, destination, input in backarcs:
   # For each state directly reachable
   # from the first state reattach 
   # all inbound transitions 
   # to the new state
   new = make_new_accepting_state()
   remove_transition(source, destination, input)
   add_transition(source, new, input)
   outbound = [(arc.input, arc.destination) for arc in arcs_from(new)]
   for input, destination in outbound:
     # Bounce back from the new state
     # to the states immediately
     # reachable from source state
     add_transition(new, destination, input)

The code tries to be more or less Python. Auxiliary functions do what their name suggests. The basic idea is as follows:

A DFA can accept words of length 1 in only these two scenarios:

  1. It loops on some input in the first accepting state.
  2. The state directly linked from the first state is accepting.

Below is the procedure to remove these accepting states while accepting all other inputs.

  1. If the first state loops on some inputs add a new state $q_1$, remove all transitions from $q_0$ to itself and add transitions for the same inputs from $q_0$ to $q_1$. Add transitions on all inputs from $q_1$ back to itself.

    For any input which on which $q_0$ used to loop $B$ now necessary makes at least two transitions before accepting it, possibly accepted string with prefixes that did not cause the automate to loop on $q_0$ are still accepted (nothing has changed).

  2. For each accepting state $q_n$ directly linked from $q_0$ we do the following:
    • change $q_n$ from accepting to non-accepting.
    • add a new accepting state $q_2$.
    • remove transitions from states $Q_i$ directly leading to $q_n$, unless they originate in $q_0$, for each transition removed add a new one for the same input from $Q_i$ to $q_2$.
    • for each outbound transition from $q_n$ add new transition on the same input from $q_2$.

Most proofs related to automata I've read so far use structural induction for similar tasks, but I cannot think about a way to approach the proof. The difficulty is in ensuring that all strings accepted by $A$ are still accepted.

PS. I have the pseudocode set in LaTeX, if it is necessary, I can add it to the post.

$\endgroup$
  • 7
    $\begingroup$ Why not construct an automaton that accepts all strings of length $\ge 1$, and then take the product automaton? $\endgroup$ – Shaull Sep 6 '15 at 15:43
  • $\begingroup$ @Shaull Thanks! I don't know what product automation is (I'm reading about it now: my understanding so far: at each node of one automaton add the entire other automaton?), but I'm probably not supposed to use it for this task. The other reason: I want this to be minimal in terms of actual programming operations to perform: i.e. only to replace the minimum required number of states. $\endgroup$ – wvxvw Sep 6 '15 at 16:09
  • $\begingroup$ PS. Also this won't work if the original automaton accepted strings of 0 length. Or am I missing something? $\endgroup$ – wvxvw Sep 6 '15 at 16:21
  • $\begingroup$ The product automaton accepts the intersection of the automata (if you define the acceptance condition accordingly, to be $F_1\times F_2$). If you want a minimal DFA, simply run a DFA minimization algorithm (e.g. using Myhill-Nerode equivalence classes). It would mean you have quite a lot of reading to do, but that would definitely get you what you want. $\endgroup$ – Shaull Sep 6 '15 at 16:48
  • $\begingroup$ @Shaull thanks again for the pointer, but by minimal I meant minimal effort to do the transformation. Constructing product automata seems at least to be quadratic in number of states of one of the automata. And the subsequent minimization will probably take its tall... what I'm trying to do is to make minimum modification to the original automata, and that should be linear in the worst case (but most likely will either do nothing at all or add at most the number of states as the size of the alphabet. $\endgroup$ – wvxvw Sep 6 '15 at 16:56
2
$\begingroup$

Basically, the answer is what @Shaull says in the comments: construct a product automaton with the one that accepts all strings of length unequal 1. What we use here is the fact that regular languages are closed under intersection. The product construction takes two automata, and simulates them in parallel. States are pairs of states of the original two automata. The combination accepts if both components accept.

But you ask for "minimal operations". So, have a look at what is in fact the automaton that accepts strings of length not 1. It simply has three states "zero", "one" and "many" with a loop for each letter at the last state. It simply counts letters up to length two (and then keeps in that state).

The product construction for this specific automaton is rather straightforward. Set aside a copy of your original automaton $A$. (You might add label "many" to each of the states, but that is extra.) Now add to these fresh copies of the original initial state and all states reachable in one step from the initial state. If the initial state has a loop, it is copied twice. (If you fancy it these get extra labels "zero" and "one"). Now remove final states from the "one"s and copy the original wiring.

Like I said, this is just a particular case of the product construction. In fact it might be even what is in your own pseudo code.

$\endgroup$
1
$\begingroup$
  1. Create a new starting state, which is accepting/non-accepting according to the original starting state. (The original starting state is still included, but is no longer the starting state.)
  2. Identify all accepting states that can be reached in one transition from the starting state
  3. Create new non-accepting states with the same outbound transitions as the states found in step 2.
  4. Create transitions from the new starting state to each state created in step 3.
  5. Create transitions from the new starting state to each non-accepting state reachable from the original starting state.

All inputs of length one now go to a non-accepting state.

(Updated: original answer was essentially steps 2 through 4 operating on the original starting state.)

$\endgroup$
  • $\begingroup$ Unless I'm misreading your answer, it won't work. Consider a 1-state DFA with input alphabet $a$. Let the start state be final and have a single transition on $a$ from the start state to itself. Obviously the language of that machine is $a^*$. It appears that your construction will yield a DFA whose language is $(aa)^*$. $\endgroup$ – Rick Decker Oct 6 '15 at 19:35
  • $\begingroup$ Step two will create a non-accepting state with $a$ going to the original state, step three will change the transition from the original state to go to the new state, so my answer will yield a DFA whose language is even-length strings. $\endgroup$ – ShadSterling Oct 6 '15 at 19:45
  • $\begingroup$ My mistake was assuming no other transitions go to the initial state. That could be fixed by duplicating the initial state first. $\endgroup$ – ShadSterling Oct 6 '15 at 19:46
-1
$\begingroup$

The simplest way to do this is to add a new starting state, with transitions exactly like the original starting state. If the new state isn't final, the result doesn't accept $\epsilon$, and you are done. If the starting state of the original automaton isn't accepting, none of this is needed.

$\endgroup$
  • 1
    $\begingroup$ Just making sure: the requirement is that words with length 1 are not accepted, what you seem to be doing is removing the empty string from the language, or am I wrong? I.e. accepting $\epsilon$ isn't a problem, if the original accepted it, so should do also the clone. $\endgroup$ – wvxvw Sep 6 '15 at 17:18

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.