0
$\begingroup$

Here is a description I read from one of the sources about 2WNFA:

"Unlike ordinary finite automata, a 2DFA needs only a single accept state and a single reject state. We can think of it as halting immediately when it enters one of these two states, although formally it keeps running but remains in the accept or reject state. The machine need not read the entire input before accepting or rejecting. Indeed, it need not ever accept or reject at all, but may loop infinitely without ever entering its accept or reject state."

I am unclear what it means by: "..The machine need not read the entire input before accepting."

For example in the automata M = ({qo, ql, q2, q3, q4, q5}, {1}, δ, qo, {q5}) (δ is transition function, L=Left, R=Right) and the transitions being:

δ(q0, 1) = (q1, R);
δ(q1, 1) = (q2, R); δ(q2, 1) = (q3, L); δ(q3, 1) = (q4, L); δ(q4, 1) = (q5);

Does the above 2WNFA, accept any string (example: "1") as the first 4 transitions can be ignored as they bring the machine back to the 1st character in the input string, thus for the last transition to the final accepting state a single 1 is enough? On other hand I think the language it accepts is empty?

Terribly confused because of the bidirection along with above explanation.

$\endgroup$
2
$\begingroup$

Unlike ordinary finite automata, a 2DFA needs only a single accept state and a single reject state.

Finite automata do not need more accepting states. Well, non-deterministic FA don't; just add two final states and appropriate $\varepsilon$-transitions. Deterministic FA, though, need multiple final states; above construction doesn't work, and Myhill-Nerode tells us that we indeed get multiple final states for some languages.

Unlike ordinary finite automata, a 2DFA needs only a single accept state and a single reject state.

If you add rejecting states to finite automata (an easy enough exercise), neither do finite automata. Consider, for instance,

$\qquad L_0 = \{ w \mid w_1 = 0 \} \cap L$

for any regular $L$. Then, a finite automaton for $L_0$ can reject immediately if the first symbol is not a $0$.

In summary, I think the authors try to read meaning into arbitrary syntactical differences.

That said, note how 2DFA need a rejection state for the stated reason: there is no natural "end of computation".

$\endgroup$
  • $\begingroup$ Much Thanks. Added some clarity to the definiton part. In the above example (I randomly generated), is the accepted language empty? I think it is but need confirmation. Moreover, I think the generic emptiness problem for even unary language seems difficult if the above example is empty? $\endgroup$ – TheoryQuest1 Aug 26 '16 at 10:41
  • $\begingroup$ @Raphael But deterministic "ordinary automata" do need more than one final(accepting) state? Even non-minimal ones? As far as I know the minimal number of final states in any deterministic automaton is at least the number of final states in the minimal automaton. $\endgroup$ – Hendrik Jan Aug 27 '16 at 1:03
  • $\begingroup$ @HendrikJan I thought of adding a single final state of each type, but you may be right in that we will need non-determinism to get that. Do you have a reference for that lower bound? $\endgroup$ – Raphael Aug 27 '16 at 9:52
  • 2
    $\begingroup$ @Raphael Yes your intuition is OK, one needs nondeterminsim or a marker for the end-of-input (which two way automata usually have) so at the end one can move to the proper end-state. By my knowledge the "reference" is just looking again at the Myhill-Nerode Theorem: two strings from different classes cannot end in the same state, which also holds for classes that belong to the language (hence end in a final state). As you know a complete class is just entirely in or out of the language. $\endgroup$ – Hendrik Jan Aug 28 '16 at 13:22

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.