Tuesday, February 20, 2007

Minimal consistent DFA revisited

I'm glad we ended up putting this problem on the midterm (as extra credit). A handful of folks nailed it dead-on, but it's still causing confusion for some -- which means it's a good one to work out! Now that it's been assigned and graded, the readers are invited to say anything and everything they want about it in the comments.

BTW, the problem of finding the minimal consistent DFA is NP-hard; this fact more or less motivates the line of research I'll be presenting at this talk tomorrow (today).

No comments: