I have been investigating "learning automatas", and I came across reference to Gold's papers several times: "Complexity Of Automaton Identification From Given Data", and "System Identification Via State Characterization", and I am confused now.
I also checked Is finding the minimum regular expression an NP-complete problem? but I am still confused.
Let us call Problem 1: Finding a minimum regular expression for a given regular expression which has same language L.
Let us call Problem 2a: Finding automaton which can explain some data D.
Let us call Problem 2b: Finding an automaton with minimum states for Problem 2a.
In "Complexity of Automaton.." paper, it states that
"However, it is the objective of this paper to show that the construction of a minimum state automaton which agrees with given data is, in general, computationally difficult."
Then later, in Theorem 2:
"Minimum Automaton Identification Question Qmin(D, n). Given: data D, positive integer n. Question: Is there a finite automaton with n states which agrees with D ?
Now, I can easily create an automaton which fits the data. Lets call it G. I can also minimize G to get G*, and count the number of states.
As I wrote the whole question, I realized that if the answer to the following statement is "NO", then I do need further help. If the answer is "YES", elaboration is appreciated, but a simple yes will clear lots of confusion.
Given arbitrary automaton G for language L, if we use some Polynomial algorithm to minimize it to G* (and P =/= NP), can there exist another smaller automaton S < G (in number of states) such that language of S is exactly L?
If answer is "NO", please proceed. If the answer is "YES", feel free to elaborate. Any help is appreciated.
- Gold assumes that a blackbox can be "identified in the limit". However I find that an a regular expression: ab(ab*)* to not apply here, since we don't know the number of states in the FSM we are trying to identify. Hence, this makes me believe Problem 1 is different than Problems 2a and 2b. Correct?
- Given the data, I can easily create an automaton, then minimize it. Based on what I've seen (and yet don't understand), the minimal automaton G* is not necessarily the "minimum automaton which can explain the data". There is confusion about what "explain the data" mean. If I minimize G to get G* some known polynomial algorithm, wouldn't that be "Exact" fit for the data? meaning all the data is accepted by G* and G*'s language is only all the data?
- Depending on how second question is answered, if there could be another smaller automaton which is difficult to obtain, then that should imply that polynomial minimization algorithms may produce different "minimal" automaton, based either on the algorithm, which I find absurd, or based on the "initial constructed automaton".
I think question 3 is absurd, which is forcing me to believe that Gold meant something specific with "agrees with given data".
Any help is appreciated.