Re: Mathematical definition of automata?

On May 17, 5:55 pm, Vadim Tropashko <vadimtro_inva...@xxxxxxxxx>
wrote:
Is there automata model without start and stop state?

A state diagram: a labelled directed graph.

The path-closure of the graph has the following elements:
(1) the set V of vertices of the original graph
(2) an identity transition I_v: v -> v, for each vertex v in V
(3) the labelled edges p: v -> v' of the original graph
(4) the product (fg): v -> v'' of any two edges f: v -> v' and g: v' -
v'' of the graph.
(5) (typed) identity property: 1_v f = f = f 1_v', if f: v -> v'
(6) (typed) associativity property: (fg)h = f(gh), if f: v -> v', g:
v' -> v'', h: v'' -> v'''.

That defines none other than the mathematical structure known as a
Category. A Category is a typed algebra modelled on the monoid:
1x = x = x1; (xy)z = x(yz),
with the above-mentioned type restrictions. Categories are also used
in developing the foundations of mathematics (so, some people go all
glossy eyed over them at their mere mention as if there were anything
more than a mere typed algebra), but that's neither important or
relevant here.

The path closure construction is the standard method by which a
Category is freely generated from a labelled directed graph. This is
the typed analogue of constructing a free monoid X* from the set of
sequences of elements from X.

Nothing in the foregoing requires V to be a finite set. Each of the
models higher up in the hierarchy beyond the FA defines a family of
infinite state automata.

These ideas are developed fully in the following:

===========

The Untold Story of Formal Languages
Part 3: The Algebraic Representation of Automata
http://federation.g3z.com/CompSci/index.htm#Untold3

This section features the introduction of an algebra for state
diagrams. Treating a state diagram as a graphical representation of a
matrix, one can define the operations of addition and multiplication
over them. The result is an extension of the cycle notation used for
representing groups.

The classes of automata seen in classical formal language and automata
theory may all be seen as instances of a general "infinite state
automata" model. What distinguishes each class is (a) the factoring of
its state space into the product of a "control" space and "device"
space; (b) the imposition of "selection" rules constraining the
allowable transitions in the device space and (c) the imposition of
"symmetry" rules governing the transitions in device space that allow
an set of transitions to be generated from a finite set. Features (b)
and (c) play roles analogous to that played by selection rules and
symmetry in non-linear dynamics.

In this section, the notion of automata and state diagrams as
graphical representations of systems of inequalities is developed.
This concept leads us directly to the issue of operator algebras and
their matrix representations.

Contents
3.1. State Diagrams, Automata and Matrices
3.2. Infinite State Automata
3.3. Varieties of Infinite State Automata
3.4. Representation of an Automataonn as a System of Inequalities
3.5. Connection to the Operator and Matrix Algebras

===========

Parts 4 and 5 are also included in the PDF found on the link. These
play out the point raised in part 3 to its logical conclusion -- the
development of algebras moulded on the celebrated "regular
expressions" for the class of languages corresponding to 1-stack
machines and 1-tape machines.

Part 4. Context-Free Expressions and the Bra-Ket Algebra
The class of infinite state automata corresponding to the 1-stack
automata can be directly converted via into a finite linear system of
inequalities over an algebra that incorporates the Bra-Ket algebra.
The resulting expressions extend the classical theory of regular
expressions up to type 2 in the Chomsky hierarchy and so may be termed
context-free expressions.

A process for converting the non-linear systems of inequalities that
represent grammars in extended BNF is also developed. A central
feature of this conversion is the process of linearization, which may
be likened to that seen in mathematical physics of taking the spinor
"square root" of a vector. With the use of the bra-ket operators, the
non-linear systems representing context-free grammars are decoupled
into first-order systems.

Contents
4.1. The Bra-Ket Algbera; Tensor Products
4.2. Infinite State Automata and Bra-Ket Notation: Example
4.3. Reduction of Push-Down Automata to Regular Bra-Ket Grammars
4.4. Embedding Context-Free Languages in C2 >< RX*
4.5. Example
4.6. Context-Free Expressions and Fixed-Point Systems: Examples
4.7. Converting EBNF Grammars and Fixed-Point Systems to Bra-Ket Form
4.8. Optimizations

4.8.1. Performing Equivalence Tests
4.8.2. Removing Uninformative Operators
4.8.3. Other Optimizations

Part 5. Turing Expressions and Translation Expressions
Taking this process one step further, we can go further and also treat
machine and automata models that employ multiple stacks or double-
ended queues. Along the way we reproduce the classical result that
links open-ended queues to stacks, and double-ended tapes to twin-
stacks.

An operator algebra for Turing machines and Turing transducers is
constructed from the Bra-Ket algebra. The parsing/translation problem
is formulated in the general setting, where we show that the
complexity of the representation of a set of outputs corresponding to
a given input under translation is linear. Though not well-known, this
is actually a somewhat trivial consequence of Kolomogorov complexity
theory. The representation provided here is a realization of the
theoretical result.

Contents
5.1. An Expression Algebra for Turing Languages and Transductions
5.2. Conversion of an Open-Ended Queue to a Stack
5.3. Reduction of Turing Machines via the Bra-Ket Algebra
5.4. Lienar Bounded Turing Machines and Context-Sensitive Expressions
5.5. Translation Systems and the Markov Machine

==============

Finally, part 2 in the following

Context Free Expressions
http://federation.g3z.com/CompSci/index.htm#Luecke

helps explain the correspondence between Fock spaces and Queue-based
automata which underlies the Bra-Ket algebra that figures centrally in
the development of context-free expressions, turing expressions and
translation expressions.

.

Relevant Pages

  • The Ghost of Von Neumann: Automata and Physics
    ... this details a synthesis of formal language and automata ... theory essentially within the setting of unversal algebra and category ... The Algebraic Representation of Formal Languages ... Varieties of Infinite State Automata ...
    (sci.physics.research)
  • Re: How Lisps Nested Notation Limits The Languages Utility
    ... Constructing large expressions by scribbling is error-prone and not ... Those who manipulate symbolic algebra without benefit of a mechanical ... display has its purpose, and compact input may have its purpose, but ... Or, if you prefer a more obscure analogy, infix algebra is like ...
    (comp.lang.lisp)
  • Re: a union is always a join!
    ... I was going by Darwen's appendix "A New Relational Algebra", ... Then we can define NOT= DOMMINUS R. ... you could allow non-query expressions but not queries in NOT ...
    (comp.databases.theory)
  • Implementing a graph algebra
    ... I am implementing a graph algebra designed to serve as a the query plan ... component of a graph-based database system. ... looking for ways to optimize expressions of higher order e.g. ...
    (comp.theory)
  • Implementing a graph algebra
    ... I am implementing a graph algebra designed to serve as the query plan ... component of a graph-based database system. ... looking for ways to optimize expressions of higher order e.g. ...
    (comp.databases.theory)