[kathy025]

Hi guys,

We're just starting with NFAs so this is probably a very basic one. As I understand it, when q0 receives 0, it can go to q2 immediately because of the e-transition.

I'm wondering why there is no q2 under the e-column for q0?

(This is from our lecture slides.)

This post has been edited by kathy025: 09 February 2016 - 09:59 PM

[macosxnerd101]

Because q_{2} \not \in \delta(q_{0}, \epsilon). That is, q_{0} cannot freely transition to q_{2}. You must read in 0 at q_{0} before that two-step transition can happen.

[kathy025]

macosxnerd101, on 10 February 2016 - 12:58 PM, said:

You must read in 0 at q_{0} before that two-step transition can happen.

Hi mac,

Can you elaborate a bit on this?

[macosxnerd101]

The table you have is a transition table. The transition function \delta(q_{i}, x) is the set of states you can reach from q_{i} upon reading in the single character x. That is, these are single transitions. So if I'm at q_{0}, there is no transition defined for the empty string. However, if I read in 0 at q_{0}, I transition to q_{1} since q_{1} \in \delta(q_{0}, 0). Then at q_{1}, I can freely transition to q_{2} because q_{2} \in \delta(q_{1}, \epsilon).

Does this make more sense?

[kathy025]

We must be having a very simplified version of theocom since I don't know how to read those conventions haha.

So epsilon means "empty string" and there is no edge defined for an empty string for q0 hence why the epsilon column for it is blank?

Sorry please don't eat me.

[macosxnerd101]

I'm using LaTeX syntax. It's standard for writing mathematics (or in any theoretical discipline). You can use this tool to translate my LaTeX to readable math (https://www.codecogs.com/latex/eqneditor.php).

Quote

So epsilon means "empty string" and there is no edge defined for an empty string for q0 hence why the epsilon column for it is blank?

That is correct.

As an aside- the transition functions for Automata need only be partial functions (i.e., not totally defined, as you are seeing in your transition table with the blank slots). If you find yourself glossing over recursive function theory (another model of computation), you'll hear the phrase "partial recursive function" come up a lot. This is the relevance.

[kathy025]

Thank you very much for your elaborations, mac!
And also for telling me about the LaTeX syntax.