NFA behaviour with "empty string"
- From: "niclane" <niclane@xxxxxxxxxxxx>
- Date: 23 Jun 2005 12:26:41 -0700
Hi,
I'm just looking for some clarification regarding how the "empty
string" label is processed by NFAs. It looks like I don't quiet
understand it correctly so I have these questions that come from the
book Intro to the Theory of Computation by Sipser:
Q1] In Example 1.56 it provides the following transformation for a
regular expression (i used @ for the accepting state):
a.b
transforms to
-> O - a -> 0 - "empty" -> O - b -> @
why is the middle "empty" transition necessary? wouldn't the NFA
function without it?
Q2] In Example 1.35 the book says that figure 1.36 accepts
"empty",a,baba and baa. I don't see how "empty" or a are accepted. The
NFA is:
has states q1,q2,q3
has start state of q1
has accept state of q1
has trasitions of the following:
q1,b -> q2
q2,a -> q2
q2,(a,b) -> q3
q1,"empty" -> q3
q3,a -> q1
How can it accept "empty" if "empty" goes to q3 but q3 is not an accept
state? how can it accept a for that matter?
Thanks for the help,
Nic
.
- Follow-Ups:
- Re: NFA behaviour with "empty string"
- From: Rick Decker
- Re: NFA behaviour with "empty string"
- Prev by Date: Re: NP-complete and NP-Hard?
- Next by Date: Oh, forgot other question regarding regular expressions
- Previous by thread: CfP : Workshop on Model Design and Validation (MoDeVa) at Models
- Next by thread: Re: NFA behaviour with "empty string"
- Index(es):