0

Suppose a finite automaton reaches a state s after processing a word w. How can we tell whether w belongs to the language (or not) of the automaton if s is final or non-final, and the automation is a DFA or NFA (4 cases).

This has been bugging me.. Any help will be much appreciated!

jason
  • 1
  • 1
  • Could you add a little more description about the problem you have? – abarisone Apr 28 '15 at 09:33
  • This was the question I'm stuck on :( It's one of the questions we had in class but I couldn't figure it out. It asked if there's any ways we can tell a word belongs to the language after it reaches a state S.. And if we can tell whether state S is final state or not, and if this automation is DFA or NFA.. – jason Apr 28 '15 at 10:36
  • @jason your question is not clear. I would suggest read your text book again. Anyways, -- NFA and DFA are two forms of FA (Finite automata) read [this post](http://stackoverflow.com/a/15661281/1673391). And a States in FA can be either Final or Non-Final state. If after procession a string `w` last state is final then string w is considered as accepted. I would suggest you to read [asking questions on StackOverflow](http://stackoverflow.com/help/how-to-ask) – Grijesh Chauhan Apr 28 '15 at 13:46

1 Answers1

0

A FSA for language L, after reading w, can stop in a set of states Qw . w is then a member of L if and only if there exists at least one final (accepting) state qf in Qw. In other words: if the FSA, reading w, can stop in a final state, then w is a member of L.

A DFA, reading the same input, will always arrive at the same state; hence the name. So here Qw always consists of a single state, and the answer is easy: if the state is a final state, than w is a member of the language; otherwise, it is not.

NFA are trickier, because if you run it on w, it might stop at any state in Qw. If it is an accepting state, by definition, you know that w is a member of L. Whew, lucky! But what if, after reading w, we reach a non-final state? Can we say, similarly to the DFA, that w is not a member of L?

Unfortunately, not*. Let's consider these two NFA:

  • NFA1, reading w, can stop in qnf1 and qnf2, both non-final states;
  • NFA2, reading w, can stop in qnf1 and qnf2, but also in qf, a final state.

Let's say that we fed w to our machine and it stopped in qnf1. What can we say about w, without knowing which NFA we are testing? Clearly nothing: w is a member of L2, because if we kept running NFA2 on w, sooner or later we might end up in qf ; on the other hand, w is not a member of L1, because no matter how many times we run w through NFA1, we can only end up in non-accepting states.

So to sum it up:

  • DFA, final state: yes
  • NFA, final state: yes
  • DFA, non-final state: no
  • NFA, non-final state: we don't know

* I assumed that the FSA are black boxes to us, and all we can observe is the word w and the state we stop in, q. If we knew the structure of the FSA, the NFA case would be much simpler, because we could just check Qw.

David Nemeskey
  • 640
  • 1
  • 5
  • 16