Finite automaton

The grammars for regular languages can be conveniently specified by finite state transition graphs for the finite automata that recognize them. The vertices of the graph represent the the system states Cj E and the arcs represent the possible input states Uj A. The arrows point to the next state that will result from the initial state when the input on the arc is applied. 

Finite automata such as these are the simplest kind of computational model, and are not very powerful. For example, no finite automaton can accept the set of all palindromes over some specified alphabet. They certainly do not wield, in abstract terms, the full computational power of a conventional computer. For that we need a suitable generalization of the these primitive computational models. Despite the literally hundreds of computing models that have been proposed at one time or another since the beginning of computer science, it has been found that each has been essentially equivalent to just one of four fundamental models finite automata, pushdown automata, linear bounded automata and Turing machines. 

Regular Languages allow only those productions that are of the form a —> era or a —> (T. Recognized by Finite Automata. 

The computational capabilities of finite automata are actually very limited. Consider, for example, the problem of constructing an arithmetic expression parser . 

Push-down Automata push-down automata generalize finite automata by introducing an internal memory. Just as for finite automata, push-down automata have a finite input alphabet and a finite set of intermediate states, a subset of which constitutes the set of its output (or accepting) states. The difference is that push-down automata have an additional stack-space, consisting of some or all of the symbols of the machine s alphabet (along with perhaps some additional symbols to be used as internal markers) which they can use to store information for later use. We can therefore generalize our definition for finite automata (equation 6.4) to ... 

HarF67d Harary, F., Palmer, E. M Enumeration of finite automata. Inf. and Control 10 (1967) 499-508. 

HarM65 Harrison, M A. A census of finite automata. Canad. J. Math. 17 (1965). 

CFD may be loosely thought of as computational methods applied to the study of quantities that flow. This would include both methods that solve differential equations and finite automata methods that simulate the motion of fluid particles. We shall include both of these in our discussions of the applications of CFD to packed-tube simulation in Sections III and IV. For our purposes in the present section, we consider CFD to imply the numerical solution of the Navier-Stokes momentum equations and the energy and species balances. The differential forms of these balances are solved over a large number of control volumes. These small control volumes when properly combined form the entire flow geometry. The size and number of control volumes (mesh density) are user determined and together with the chosen discretization will influence the accuracy of the solutions. After boundary conditions have been implemented, the flow and energy balances are solved numerically an iteration process decreases the error in the solution until a satisfactory result has been reached. 

A very nice general tutorial of HMMs is given in (Rabiner, 1989). An extension of HMMs from finite automata (which is the deterministic version of a Markov chain) to context-free languages leads to the concept of a stochastic context-free grammar. Such grammars have been used in an analogous way to predict RNA secondary structures (Grate et al., 1994). 

K. Culik and J. Kari, Image compression using weighted finite automata. Comput. and Graphics, 17 (1993), 305-313. 

Balcazar, J.L., Diaz, J., Gavald., R., Watanabe, O. Algorithms for learning finite automata from queries a unified view. In Du, D.Z., Ko, K.I. (eds.) Advances in Algorithms, Languages, and Complexity, pp. 73-91. Kluwer Academic Publishers, Dordrech (1997)... 

Rivest, R.L., Schapire, R.E. Inference of finite automata using homing sequences. Inf. Comput. 103(2), 299-347 (1993)... 

Keywords Grammar inference k-Testable language in strict sense Probabilistic deterministic finite automata Timed-transition systems Evolution of elderly people disability... 

We are interested by the class of regular grammars that are the simplest class of formal grammars in the Chomsky hierarchy and it consists in the identification of the corresponding learning of deterministic finite automata (DFA). 

A finite automaton with transition probabilities represents a distribution over the set of all strings defined over a finite alphabet. The articles [18, 24] present a survey and a study of the relations and properties of probabilistic finite-automata and tree. The article [10] clarifies the links between probabilistic automata and Hidden Markov Models (HMM). In a first part of this work, the authors present ... 

The authors show that one the one hand, probabilistic deterministic finite automata (PDFA) form a proper subclass of probabilistic non-deterministic automata (PNFA) and the other hand, PNFA and HMM are equivalent. 

Learning a Deterministic Finite Automata (DFA) of timed-transition systems by using an extension of k-TSSI algorithm. 

Finite Automata with Translucent Letters Applied in Natural and Formal Language Theory... 

Keywords Finite automata Mildly context-sensitive languages Natural languages Formal linguistics Free-order languages Computational linguistics Formal models... 

This paper is structured as follows. In Sect. 2 we recall the definition of the finite automata with translucent letters and we also present an example. In Sect. 3 the parsing problem is considered with some further examples, while in Sect. 4 we consider the extension of regular languages by permutations. Further, in Sect. 5 we show examples for the usage of finite automata with translucent letters modeling... 

In this section we fix our notation and recall the definition and some basic facts about the finite automata with translucent letters. 

Now we recall a recently developed variant of the nondeterministic finite automata that does not process its input strictly from left to right [19]. 

The classical nondeterministic finite automata (NFA) is obtained from the NFAwtl by removing the endmarker 8 and by ignoring the translucency relation T, and the deterministic finite-state acceptor (DFA) is obtained from the DFAwtl in the same way. Thus, the NFA (DFA) can be interpreted as a special type of NFAwtl (DFAwtl). Accordingly, all regular languages are accepted by DFAwtl. Moreover, DFAwtls are much more expressive than standard DFAs as shown by the following example. 

---