Automata Games, Stochastic Automata and Formal Languages

摘要

The report is mainly concerned with the behavior of a class of learning automata operating in random environment and a preliminary study of relating automata theory to formal languages. Based on the strategies of two-armed bandit problems, two sequential learning models having deterministic and stochastic transition rules, respectively, are proposed. Based on the iterated logarithm inequality, confident automation A is formulated which is able to find the optimal action in finite time. The learning composite fuzzy automaton operating in a random environment has shown the desired property of asymptotic optimality. Applications of the learning automata to pattern classification and feature selection have also been considered. Computer simulated examples for the applications of the proposed models include games against nature and two-person zero-sum games. A survey is given concerning the basic concepts and properties of phrase-structure languages.