?

Log in

No account? Create an account
Stuff I don't care about: Problem 1: 2.3.1 (83) Imagine you have an… - brad's life — LiveJournal [entries|archive|friends|userinfo]
Brad Fitzpatrick

[ website | bradfitz.com ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

[Apr. 27th, 2000|10:20 pm]
Brad Fitzpatrick
Stuff I don't care about:

Problem 1: 2.3.1 (83)
Imagine you have an NFA N(L), and then you do the subset construction to find the equivalent DFA D(L). Now, the final states of D(L) are any states which in their set contain at least one final state of N(L). If you then invert the states, the final states are any node which does not contain a final state of N(L), and this exactly what we want. However, let's see what happens if we try the naive way to invert the NFA N(L) by flipping all the states. Let's call this inverted NFA ~N(L). The final states of ~N(L) are now the old non-final states. Now, if we go to take the subset construction of ~N(L), the final states of ~D(L) are any node which contain at least one non-final state. However, there's nothing saying that the final states of ~D(L) can't also contain final states. Thus, inverting the states of an NFA do not create the complement, else the equivalent DFA of the inverted NFA would have its final nodes all consisting of sets that were previously entirely non-final.

LinkReply

Comments:
[User Picture]From: dpb
2000-04-27 10:56 pm (UTC)

?!?

Um....right....is that for real?
(Reply) (Thread)
[User Picture]From: bradfitz
2000-04-27 10:58 pm (UTC)

Re: ?!?

Damn straight. And that's the easy one, problem 1. You should see the rest... can't put them up because most of them are drawings. (no scanner, but like you'd really want to see them anyway..... ugh....)
(Reply) (Parent) (Thread)
[User Picture]From: eli
2000-04-27 11:44 pm (UTC)

Answer

The answer is False
(Reply) (Thread)
[User Picture]From: erik
2000-04-28 12:19 am (UTC)

Re: Answer

No way dumbass, the answer is 7.. the answer is *always* 7.
(Reply) (Parent) (Thread)
[User Picture]From: righellis
2000-04-28 02:14 am (UTC)

Re: Answer

Nah dude, fuck that, it has got to be "C"
(Reply) (Parent) (Thread)
[User Picture]From: nolegs
2000-04-28 04:54 am (UTC)
the answer is 7
(Reply) (Thread)
(Deleted comment)
[User Picture]From: bradfitz
2000-04-28 09:39 am (UTC)

Re: Well...

Yeah, but what's the question? :-)
(Reply) (Parent) (Thread)
From: (Anonymous)
2000-04-28 03:14 pm (UTC)
My hell-- and I thought HTML was tough at times.....
(Reply) (Thread)