Re: NFA behaviour with "empty string"
- From: Rick Decker <rdecker@xxxxxxxxxxxx>
- Date: Thu, 23 Jun 2005 22:28:02 -0400
niclane wrote:
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?
In this case, yes, it would. In general, though, with a and b replaced by arbitrary regular expressions, it might not. I suggest you look at Sipser's explanation in the "proof idea" of Theorem 1.47. As an example of where this "merge the final state of the first with the start state of the second" scheme fails, consider
FA1: start p1
accept p2
transitions
p1,a -> p2
p2,b -> p2Clearly, L(FA1) = ab*
FA2: start q1
accept q2
transitions
q1,a -> q1
q1,b -> q2We see L(FA2) = a*b
Now if we simply merged p2 and q1 in the hope of getting a FA for (ab*).(a*b) we'd have
FA3: start p1
accept q2
(merged state s = p2 = q1)
transitions
p1,a -> s
s,b -> s // from FA1
s,a -> s // from FA2
s,b -> q2I'll leave it to you to show that L(FA3) isn't ab*a*b.
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?
You're conflating the two meanings of "empty" above. The rule
q1, "empty" -> q3
should be understood as meaning that the NFA is allowed to change states from q1 to q3 without reading any input symbols (which is why the NFA accepts a. Starting in q1, it changes state to q3 without reading any input. Then in q3 it reads the input character, a, and changes state back to q1, which is an accept state.
On the other hand, you surely know that a finite automaton accepts a string w if, after having read all of the input, it is in a final state. In your example, since the start state is an accept state, it will accept the empty *string*, since it can be in the accept state after having read all of the (no) characters in the empty string. In your example, if the NFA is given the empty string as input, it can be in either of states q1 or q3. Since q1 is an accept state, the automaton accepts the empty string.
This is a common misunderstanding, caused in part by the fact that almost all authors use the same symbol to represent the empty string and the "spontaneous" transition from one state to another without consuming any input symbols.
Regards,
Rick
.
- References:
- NFA behaviour with "empty string"
- From: niclane
- NFA behaviour with "empty string"
- Prev by Date: Re: to CNF efficiently
- Next by Date: Re: Oh, forgot other question regarding regular expressions
- Previous by thread: NFA behaviour with "empty string"
- Next by thread: Oh, forgot other question regarding regular expressions
- Index(es):
Relevant Pages
|
