0
$\begingroup$

I am reading this example of FSA from book Martin & Jurafsky "Speech and Language Processing". enter image description here

As per definition of FSA you can only transition to one state after consuming one input. In this example if the input is say "twenty" to which state it will transition q2 or q1 ? Say if the input was "twenty one". After consuming first string which state it will transition to?

$\endgroup$
  • $\begingroup$ Welcome to Computer Science! The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Jan 24 '18 at 0:09
0
$\begingroup$

The automaton in the image is indeed nondeterministic.

You need to think a little differently about nondeterministic machines. It's no longer a question of "what happens when X?" but about "what can happen when X?". For each input, there can be many different computations, even with different outcomes.

Note how the definition of acceptance is different. For DFA, it's "the (unique) computation is accepting"; for NFA, it's "there exists an accepting computation".

Here, in your example, if the input is "twenty", there are two computations:

  1. $q_0 \to q_1$ and
  2. $q_0 \to q_2$.

Since the second is accepting, "twenty" is in the language of this automaton.


Side note: A TCS book that uses twenty as terminal symbol and generally avoids LaTeX for it's mathematics typesetting is highly suspect. I recommend that if you run into any problems, look for a standard textbook before worrying too much.

$\endgroup$
  • $\begingroup$ Thanks Raphael for the answer! So contrary to the label the automata is not deterministic. This book is referred as main textbook by our Professor. Should I point this out to him? $\endgroup$ – Ujjwal Mishra Jan 24 '18 at 0:57
  • $\begingroup$ @UjjwalMishra The label says "FSA" which, depending on the definition, is a synonym of "NFA". "DFA" would have a special label. $\endgroup$ – Raphael Jan 24 '18 at 6:14
  • $\begingroup$ @UjjwalMishra Let's assume your professor has their reasons; maybe the focus of the course is something else the book does good at? Nevertheless, for your own studies, you can (and should!) draw on other resources. $\endgroup$ – Raphael Jan 24 '18 at 6:15

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.