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:
- It loops on some input in the first accepting state.
- The state directly linked from the first state is accepting.
Below is the procedure to remove these accepting states while accepting all other inputs.
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).
- For each accepting state $q_n$ directly linked from $q_0$ we do the
- 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.