This exercise may or may not be assigned in the course I'm TAing this spring, but it's a good one to work out. It definitely had me confused at first, and I was in good company.
A teacher gives you a bunch of strings over some finite alphabet and labels each string as "positive" or "negative"; we'll refer to these labeled strings as the sample S. A deterministic finite-state automaton (DFA) is consistent with the sample S if it accepts the positive strings in S but not the negative ones. Let A0 be any DFA that is consistent with S and let A1 be the automaton obtained by minimizing A0 (by this point in the course you'll have learned efficient minimization procedures). Is A1 the smallest DFA that's consistent with S?
Please don't post the answer in the comments!
Subscribe to:
Post Comments (Atom)
3 comments:
Dear,
A single layer perceptron is an example of DFA? Do you will post the answer here?
A single layer perceptron, in finite dimensions, can compute certain Boolean functions over a fixed size input (i.e., {0,1}^n for some fixed n). A DFA can be thought of as a Boolean function over unrestricted-length inputs (i.e., {0,}^* -- all finite sequences of 0's and 1's). So in general, unless you allow infinite-dimensional perceptrons, the answer is no.
But this approach of identifying DFA's with hyperplanes is hitting very close to some of my recent work; have you been reading my papers? :)
Ok, Ok, I am a statistical physicist, so I opnly work with infinite size perceptrons... :o))
Post a Comment