Finite state automata links
From the University of Chicago:
Linguist Noam Chomsky defined a hierarchy of languages, in terms of complexity. This four-level hierarchy, called the Chomsky hierarchy, corresponds precisely to four classes of machines. Each higher level in the hierarchy incorporates the lower levels: that is, anything that can be computed by a machine at the lowest level can also be computed by a machine at the next highest level....
The levels of the Chomsky hierarchy are as follows:
MACHINE CLASS LANGUAGE CLASS
------------- --------------
finite automata regular languages
pushdown automata context-free languages
linear bounded automata context-sensitive languages
Turing machines recursively enumerable languages
The simplest kind of machine is the finite automaton, while the most complex machine is the Turing machine.
Each of these language classes are of interest to computer programmers:
LANGUAGE CLASS EXAMPLE
-------------- -------
regular languages pattern matching languages
context-free languages simpler programming languages
context-sensitive languages most programming languages
recursively enumerable languages natural languages
Languages are usually defined by grammars, so there are also classes of grammars that correspond to these language classes:
LANGUAGE CLASS GRAMMAR CLASS
-------------- -------------
regular languages regular expressions
context-free languages Backus-Naur forms
context-sensitive languages Van Wijngaarden (two-level) grammars
recursively enumerable languages ???...
A finite automaton (or finite state machine) consists of:
A finite set of states
A finite alphabet of input symbols
A state transition function, the domain of which is pairs of state X symbol, and the range of which is states.
A distinguised initial state
A set of distinguished accepting states
To run the automaton on a given input string, we simply iteratively execute the state transition function, calling it with the current state (starting with the initial state) and the current input symbol. Each time we call the function, we advance to the next input symbol, and use that with the new state returned by the function as the input to the next iteration. We terminate when we've exhausted the input string. If the process terminates with the function returning a state that's a member of the set of accepting states, we have recognized the input string; otherwise, we have rejected it.
Finite automata can be modelled with a state transition diagram, a digraph with the states represented by the nodes and the transitions represented by the arcs (labelled with symbols). For any regular language, there are an infinite number of possible finite automata that can be constructed to recognize that language....
From sakharov.net:
A Finite State Machine (FSM) is a model of behavior using states and state transitions. A transition is a state change triggered by an input event, i.e. transitions map some state-event pairs to other states. As indicated in the name, the set of states should be finite. Also, it is assumed that there is a finite set of distinct input events or their categories (types, classes). Subsequently, the set of transitions is finite as well.
The origin of FSMs is finite atomata. A Finite Atomaton is a more formal notion than a FSM....
From flightlab.com, cited at coverpages.org:
XML validation is an instance of the regular expression matching problem: given a regular expression e and a string s, is s in L(e)? (Here L(e) denotes the language accepted by e).
The most commonly-used technique to solve this problem is based on finite automata. There is another algorithm, based on derivatives of regular expressions, which deserves to be more widely known.
One of these days I'm going to get around to writing up a more complete description of the algorithm; in the meantime here is a (mostly uncommented, untested) Haskell program fragment that implements it....
From MIT:
Organizations continually strive for improvement in their processes. However, such improvement is dependent on the extent of understanding of successful processes, including possible alternative processes and their interrelationships. Because there is little systematic theoretical or empirical foundation to assist understanding of processes, the development of improved processes is hindered.
Developing a systematic theoretical or empirical foundation for understanding processes involves developing a representation of processes, in combination with a method and system for viewing the representation, which enables one to compare alternative ways to perform a task, to compare a task to similar tasks and to judge which alternative processes are likely to be useful for accomplishing the task.
Much work is available concerning representation of computer processes. Processes for computer systems are commonly represented using flow charts, data flow diagrams, state transition diagrams (which define finite state machines, push down machines, or even Turing machines), Petri nets, and specialization.
A flow chart represents a process as a series of steps, with arrows between them, which represents an order in which the steps are to be performed. Some of the steps are decision points, so depending on the circumstances, different sets of steps might be performed. A data flow diagram is similar but represents how modules of a system are interconnected to perform the steps of a process but focuses on the ordering relationships imposed by the fact that data produced by some modules is used by other modules.
A state transition diagram represents a process in terms of the possible states of the system. The steps taken in the process are the transitions that move the system from one state to another. The most powerful representation which included a state transition diagram is a Turing machine, which can be used to describe any com-
puter executing any computer program written in any computer programming language. A Petri net is similar to a finite state machine, but allows multiple states to be marked simultaneously. Transitions between states may be synchronized, since multiple states have to be marked at the same time for a particular transition to occur.
Significant developments have also been made in computer representation of objects, such as object-oriented systems. These systems rely on the concept of specialization which involves classifying specific objects into generic, more abstract classes from which they can inherit properties.
These representational paradigms for computer processes, although applicable to the representation of organizational processes lack the ability to model how processes are related and how processes may be dependent on each other in ways other than prerequisites or data flow type dependencies. More specifically, these paradigms have not been applied effectively in representing interrelationships of processes in a kind of computerized handbook which could be consulted to find a variety of alternative ways to perform particular processes, along with experience and guidelines about which alternatives work best in given situations....
From ibissoft.se:
State transition diagrams are used to model the lifecycle of a class by means of a kind of finite state automatons. Many object-oriented methods use one complex automaton that offers constructs like and-states and or-states to express hierarchical aspects of an object lifecycle, c.f. [Rum91]. In our approach we use several simple automatons for modeling the lifecycle of a class. For each state variable defined in the class diagram an automaton can be defined that shows how the values of the state variable change due to method calls. The state of an object is given by the cartesian product over the values of its state variables. Additionally, state transitions can be labeled with guard conditions in order to express dependencies between the state variables of an object. In general, state transition diagrams are useful for describing the lifecycle of data objects because of their passive character. For modeling the behavior of activity objects which are the central points of interactions we use object behavior charts.
From Nick Malik:
After showing a workflow diagram to a co-worker, he asked me if I could tell him how this is any different from basic Finite State Automata (FSA)....
For those of you who aren't familiar with FSA theory...[t]he idea is this: arrange your input into a stream of tokens of the same size. Then, keeping a state, read each token. The token will dictate the state you move to next. Side effects could be added to a transition. These side effects, taken together, were the actual functional code of the system.
In a strange way, we've all moved to FSA programming when we moved to event driven application programming....It's a bit different, though, in the sense that our input isn't in a stream. We can't look ahead at the next token or move in the other direction over a series of tokens (important parts of compilier design).
In that respect, Workflow modeling is closer to event driven programming than it is to FSA theory, because we don't have that input stream. We can't look ahead.
On the other hand, unlike event driven programming, most workflow systems use the FSA approach to modelling, where you look at the behavior of the system by creating a graph showing the stages of work, and the transitions from stage to stage.
However, what really distinguishes Finite State Automata from workflow programming, in my mind, are the three layers of abstraction inherent in Workflow analysis.
Finite State Automaton development requires a pre-processing step, where you take the input and interpret it as a series of tokens in a language. In compiler theory, we call this lexical analysis....
With workflow analysis, there are three layers of abstraction: Business unit level, Business process level, and Workstep level. All three are distinct (but related). All can be described with rules and constraints. All have a specific purpose, and each one can be represented as a state graph. The mathematics are considerably more complex. (Only the lowest level has to be deterministic). There are many PhD level practitioners of workflow modeling who can attest to the fact that workflow is much more complicated and complex than the fundamental concept of a Finite State Automaton.
Why?
Because FSA's interpret logic... nothing more.
Workflow modeling deals with human behavior.
Also see workflow terms at Apache Lenya.
Linguist Noam Chomsky defined a hierarchy of languages, in terms of complexity. This four-level hierarchy, called the Chomsky hierarchy, corresponds precisely to four classes of machines. Each higher level in the hierarchy incorporates the lower levels: that is, anything that can be computed by a machine at the lowest level can also be computed by a machine at the next highest level....
The levels of the Chomsky hierarchy are as follows:
MACHINE CLASS LANGUAGE CLASS
------------- --------------
finite automata regular languages
pushdown automata context-free languages
linear bounded automata context-sensitive languages
Turing machines recursively enumerable languages
The simplest kind of machine is the finite automaton, while the most complex machine is the Turing machine.
Each of these language classes are of interest to computer programmers:
LANGUAGE CLASS EXAMPLE
-------------- -------
regular languages pattern matching languages
context-free languages simpler programming languages
context-sensitive languages most programming languages
recursively enumerable languages natural languages
Languages are usually defined by grammars, so there are also classes of grammars that correspond to these language classes:
LANGUAGE CLASS GRAMMAR CLASS
-------------- -------------
regular languages regular expressions
context-free languages Backus-Naur forms
context-sensitive languages Van Wijngaarden (two-level) grammars
recursively enumerable languages ???...
A finite automaton (or finite state machine) consists of:
A finite set of states
A finite alphabet of input symbols
A state transition function, the domain of which is pairs of state X symbol, and the range of which is states.
A distinguised initial state
A set of distinguished accepting states
To run the automaton on a given input string, we simply iteratively execute the state transition function, calling it with the current state (starting with the initial state) and the current input symbol. Each time we call the function, we advance to the next input symbol, and use that with the new state returned by the function as the input to the next iteration. We terminate when we've exhausted the input string. If the process terminates with the function returning a state that's a member of the set of accepting states, we have recognized the input string; otherwise, we have rejected it.
Finite automata can be modelled with a state transition diagram, a digraph with the states represented by the nodes and the transitions represented by the arcs (labelled with symbols). For any regular language, there are an infinite number of possible finite automata that can be constructed to recognize that language....
From sakharov.net:
A Finite State Machine (FSM) is a model of behavior using states and state transitions. A transition is a state change triggered by an input event, i.e. transitions map some state-event pairs to other states. As indicated in the name, the set of states should be finite. Also, it is assumed that there is a finite set of distinct input events or their categories (types, classes). Subsequently, the set of transitions is finite as well.
The origin of FSMs is finite atomata. A Finite Atomaton is a more formal notion than a FSM....
From flightlab.com, cited at coverpages.org:
XML validation is an instance of the regular expression matching problem: given a regular expression e and a string s, is s in L(e)? (Here L(e) denotes the language accepted by e).
The most commonly-used technique to solve this problem is based on finite automata. There is another algorithm, based on derivatives of regular expressions, which deserves to be more widely known.
One of these days I'm going to get around to writing up a more complete description of the algorithm; in the meantime here is a (mostly uncommented, untested) Haskell program fragment that implements it....
From MIT:
Organizations continually strive for improvement in their processes. However, such improvement is dependent on the extent of understanding of successful processes, including possible alternative processes and their interrelationships. Because there is little systematic theoretical or empirical foundation to assist understanding of processes, the development of improved processes is hindered.
Developing a systematic theoretical or empirical foundation for understanding processes involves developing a representation of processes, in combination with a method and system for viewing the representation, which enables one to compare alternative ways to perform a task, to compare a task to similar tasks and to judge which alternative processes are likely to be useful for accomplishing the task.
Much work is available concerning representation of computer processes. Processes for computer systems are commonly represented using flow charts, data flow diagrams, state transition diagrams (which define finite state machines, push down machines, or even Turing machines), Petri nets, and specialization.
A flow chart represents a process as a series of steps, with arrows between them, which represents an order in which the steps are to be performed. Some of the steps are decision points, so depending on the circumstances, different sets of steps might be performed. A data flow diagram is similar but represents how modules of a system are interconnected to perform the steps of a process but focuses on the ordering relationships imposed by the fact that data produced by some modules is used by other modules.
A state transition diagram represents a process in terms of the possible states of the system. The steps taken in the process are the transitions that move the system from one state to another. The most powerful representation which included a state transition diagram is a Turing machine, which can be used to describe any com-
puter executing any computer program written in any computer programming language. A Petri net is similar to a finite state machine, but allows multiple states to be marked simultaneously. Transitions between states may be synchronized, since multiple states have to be marked at the same time for a particular transition to occur.
Significant developments have also been made in computer representation of objects, such as object-oriented systems. These systems rely on the concept of specialization which involves classifying specific objects into generic, more abstract classes from which they can inherit properties.
These representational paradigms for computer processes, although applicable to the representation of organizational processes lack the ability to model how processes are related and how processes may be dependent on each other in ways other than prerequisites or data flow type dependencies. More specifically, these paradigms have not been applied effectively in representing interrelationships of processes in a kind of computerized handbook which could be consulted to find a variety of alternative ways to perform particular processes, along with experience and guidelines about which alternatives work best in given situations....
From ibissoft.se:
State transition diagrams are used to model the lifecycle of a class by means of a kind of finite state automatons. Many object-oriented methods use one complex automaton that offers constructs like and-states and or-states to express hierarchical aspects of an object lifecycle, c.f. [Rum91]. In our approach we use several simple automatons for modeling the lifecycle of a class. For each state variable defined in the class diagram an automaton can be defined that shows how the values of the state variable change due to method calls. The state of an object is given by the cartesian product over the values of its state variables. Additionally, state transitions can be labeled with guard conditions in order to express dependencies between the state variables of an object. In general, state transition diagrams are useful for describing the lifecycle of data objects because of their passive character. For modeling the behavior of activity objects which are the central points of interactions we use object behavior charts.
From Nick Malik:
After showing a workflow diagram to a co-worker, he asked me if I could tell him how this is any different from basic Finite State Automata (FSA)....
For those of you who aren't familiar with FSA theory...[t]he idea is this: arrange your input into a stream of tokens of the same size. Then, keeping a state, read each token. The token will dictate the state you move to next. Side effects could be added to a transition. These side effects, taken together, were the actual functional code of the system.
In a strange way, we've all moved to FSA programming when we moved to event driven application programming....It's a bit different, though, in the sense that our input isn't in a stream. We can't look ahead at the next token or move in the other direction over a series of tokens (important parts of compilier design).
In that respect, Workflow modeling is closer to event driven programming than it is to FSA theory, because we don't have that input stream. We can't look ahead.
On the other hand, unlike event driven programming, most workflow systems use the FSA approach to modelling, where you look at the behavior of the system by creating a graph showing the stages of work, and the transitions from stage to stage.
However, what really distinguishes Finite State Automata from workflow programming, in my mind, are the three layers of abstraction inherent in Workflow analysis.
Finite State Automaton development requires a pre-processing step, where you take the input and interpret it as a series of tokens in a language. In compiler theory, we call this lexical analysis....
With workflow analysis, there are three layers of abstraction: Business unit level, Business process level, and Workstep level. All three are distinct (but related). All can be described with rules and constraints. All have a specific purpose, and each one can be represented as a state graph. The mathematics are considerably more complex. (Only the lowest level has to be deterministic). There are many PhD level practitioners of workflow modeling who can attest to the fact that workflow is much more complicated and complex than the fundamental concept of a Finite State Automaton.
Why?
Because FSA's interpret logic... nothing more.
Workflow modeling deals with human behavior.
Also see workflow terms at Apache Lenya.
posted by Ontario Emperor | 15:37
0 Comments:
Post a Comment
<< Home