=Paper=
{{Paper
|id=Vol-1548/025-Jerins
|storemode=property
|title=Grids of Finite Automata
|pdfUrl=https://ceur-ws.org/Vol-1548/025-Jerins.pdf
|volume=Vol-1548
|authors=Kārlis Jēriņš
|dblpUrl=https://dblp.org/rec/conf/sofsem/Jerins16
}}
==Grids of Finite Automata==
https://ceur-ws.org/Vol-1548/025-Jerins.pdf
Grids of Finite Automata
Kārlis Jērin.š
University of Latvia, Riga, Latvia
karlis.jerins@gmail.com
Abstract. Finite automata are a well known topic in computer science. Automata
read words in a given alphabet and determine if those words belong to a specific
formal language. They have been the subject of lots of research, and much is
known about their capabilities. Parallelism in automata - systems consisting of
multiple automata that read the same word - is far less researched. In this paper,
a new model of parallel calculation with automata is introduced. It is based on
the concept of cellular automata, and uses multiple automata that are arranged in
a certain grid and perform state transitions based on the states of their neighbors.
Some early results are also shown.
Keywords: deterministic automata, parallel automata, regular languages
1 Introduction
Parallel computation is an important subject in the modern day – there are ever more
and more problems that aren’t solved by throwing more memory or CPU cycles at
them, but instead require several programs to work in tandem, sharing the work load
somehow. Research in this direction is also seen in automata theory – one needs to
only consider models such as multihead automata [1] or multiprocessor automata [2].
We, however, are interested in a slightly different and somewhat constrained model –
one where all units involved in the calculations are identical. This brings to mind the
model of cellular automata – infinite grids of small, simple automata that change states
based on the current states of other automata around them. Cellular automata have been
well-researched in the past – some have even been found to be Turing-complete [3, 4].
However, they have some problems as detailed in the next chapter, and we introduce
a new model – grids of finite automata – to compensate for those problems.
2 Grids of Finite Automata
Cellular automata, though certainly an interesting subject of study, make for poor tools
for calculation. An infinite number of cells makes them close to impossible to imple-
ment, and it is hard to define when a cellular automaton can be said to have finished its
calculations, or how to interpret its output. Grids of finite automata (from here on they
will be referred to in an abbreviated form – GFA) are an answer to these problems.
A GFA, as implied by its name, consists of multiple finite automata arranged in
a grid of some sort. In the examples shown in this paper, the automata will either be
26 K. Jērin.š
arranged in one line or a rectangular grid, but other arrangements are easily available
if necessary. The component automata are all identical save for their position in the
grid (which is constant over time) and a number to identify them, and they consist of
a set of states and a state transition function. However, unlike other models that use
automata, these component automata do not have a read head and don’t actually read
symbols on an input tape. Instead, the input is transformed into a tuple of states and this
tuple is used as the initial states for the components. The state transition function is also
different – since the components have no read head, the function instead takes as input
the current states of a number of other components of the GFA. For a given component,
the components on whose states its state transitions depend are called neighbors, and
the neighbor property is symmetric – if component a is one of the neighbors for b, then
b is one of the neighbors for a.
One component of the GFA is designated as the main component. It has the same
states and transition function as all the other components, and uses them the same way,
but the main component provides one crucial function for the entire GFA. The GFA
halts the instant its main component halts (other components are allowed to halt earlier
if the state transitions indicate that they should). It also provides the answer for whatever
calculation the GFA is performing – a function maps the state set of the main component
to the set of all answers to that calculation, and thus the GFA gives its answer based on
the last state its main component was in prior to halting.
Definition 1. A GFA component is a tuple C = (Q, Q0 , n, F, A, B) such that:
– Q is a non-empty set of states
– Q0 ⊆ Q is a non-empty set of initial states
– n is the number of neighbors
– F:Q × (Q ∪ {ε})n → Q ∪ {ε} is the state transition function
– A: Q→ N is the answer function that maps the halt state of the main component to
an answer (of course, N can be substituted by other sets of answers as required).
– B : Σ∗ → Q∗0 × N is the initialization function that transforms input into a tuple of
initial states of length equal to the length of the input and the identifying number
of the main component. It is important to note that the function must be such that
the identifying number is dependent only on the length of the input word, but not
on its contents
If the state transition function is defined as written above, components are deter-
ministic automata. GFAs with deterministic components could also be called GDA –
to distinguish them from GFAs with other kinds of components. Those other kinds of
components would necessitate different definitions of the state transition function, and
are beyond the scope of this paper – thus, to avoid needlessly changing names, we will
continue to use the acronym GFA.
Definition 2. A GFA is a tuple Gk = (C, k, f ) such that:
– C is a GFA component as defined above
– k ∈ N is the number of such components (all identical)
– f : [1, k] → ([1, k] ∪ {ε})n is the neighbor function that maps each component to
a n-tuple of its neighbors
Grids of Finite Automata 27
In the state transition function definition above, ε refers to components that are either
absent or have halted – the state transition function doesn’t distinguish between these
two cases. In the neighbor function, ε refers to absent components – for example, if,
for the given GFA, components are arranged in one line and each component has two
neighbors, one to the left and one to the right, then the components at the very ends of
the line have only one neighbor each. The neighbor function indicates that by placing ε
where the missing neighbor would otherwise be.
The GFA definition above (in particular, the definition of the initialization function)
also highlights a limitation of this model – a GFA with k components can only pro-
cess words of length k. The function could be modified to work with inputs of length
up to k ∗ l for any ∈ N . As defined, the function usually will set the m-th component
to a state qsm ∈ Q0 such that sm is the m-th symbol of the input, and such modifica-
tions would initialize components to states corresponding to a string of symbols of
length l. That, however, would lead to rapid growth in state complexity for the compo-
nents – usually the set of initial states is as big as the input alphabet (and, if necessary,
a constant number of other initial states), but making each state correspond to a string
of length l would increase the initial state set by a power of l. Since that would only
decrease the number of components necessary for recognizing a word of given length
linearly, we choose not to make this tradeoff.
The previous paragraph may give the impression that a GFA cannot really be said
to solve a problem, since for every GFA there is a maximum input length it can process,
and working with longer inputs necessitates creating a new GFA. This is not so – while
it is true that the neighbor function needs to be adapted to different input lengths and
different component counts, it is important to note that the structure of the components
themselves is independent of input length – whether the input is one symbol or a billion,
the components used in solving the task at hand do not change.
Let us now define more formally the way a GFA operates:
Definition 3. A configuration of a GFA Gk = (C, k, f ) with components C =
(Q, Q0 , n, F, A, B) is a k-tuple c ∈ (Q ∪ {ε})k .
Definition 4. A GFA configuration is called an initial configuration if c ∈ Qk0
Definition 5. A GFA configuration is called a terminal configuration if qH = ε, where
H is the number of the main component
Definition 6. The GFA configuration
transition
relation `Gk holds for configurations
0 0 0 0
c = (q1 , q2 , . . . , qk ) and c = q1 , q2 , . . . , qk if and only if all these conditions are true:
– qH 6= ε 0
– ∀i ∈ N : (qi = ε) → qi = ε
0
– ∀i ∈ N : (qi 6= ε) → qi = F qi , q f1 (i) , q f2 (i) , . . . , q fn (i) , where f j (i) denotes the
j-th element of the tuple f (i)
If all these conditions are true, the configuration c0 is said to follow the configuration c
(this is denoted by c `Gk c0 ).
28 K. Jērin.š
The first condition specifies that no configurations follow a terminal configuration.
The second specifies that, once a component has halted, it cannot start again. The third
describes how state transitions take place in a GFA.
Definition 7. The output of Gk for an initial configuration c0 is a natural number z such
that there exist Gk configurations c1 c2 , . . . , cx (ci = (q1i , q2i , . . . , qki )) (for some natural
number x), for which these conditions hold:
– c0 `Gk c1 `Gk c2 `Gk . . . `Gk cx
– cx is a terminal
configuration
– A qHx−1 = z
If the output of Gk for initial configuration c0 is z, this is denoted by Gk (c0 ) = z.
Definition 8. A GFA component C = (Q, Q0 , n, F, A, B) calculates a function Φ : Σ∗ →
N if and only if for every x ∈ dom (Φ) there is a GFA G|x| = (C, |x| , f ) such that
G|x| (B (x)) = Φ (x).
3 Language Recognition with GFAs
As with many other kinds of automata, GFAs are also intended for formal language
recognition – the task is to determine if a given input word belongs to a language or not.
That is essentially the same as calculating a function Φ : Σ∗ → {0, 1}, and it is already
shown how GFAs calculate functions. This chapter will demonstrate some examples of
GFAs that recognize languages.
Theorem 1. For every regular language there is a GFA that recognizes that language.
Proof. If a language L ∈ Σ∗ is regular, then there is a minimal one-way determin-
istic automaton DFA = (QDFA , Σ, fDFA , FDFA , q0DFA ) (in order: set of states, input al-
phabet, state transition function, set of accepting states, initial state), where QDFA =
(qDFA1 , qDFA2 , . . . , qDFAX ) and Σ = (s1 , s2 , . . . , sy ) for some natural x and y, that recog-
nizes L.
Let us now create a GFA component for recognizing the language:
– Q = qDFA1 , qDFA2 , . . . , qDFAx , qs1 , qs2 , . . . , qsy (the component has as many states
as the DFA, plus as many as the size of the input alphabet)
– Q0 = qs1 , qs2 , . . . , qsy
– n = 2 (each component has two neighbors – essentially, all components are ar-
ranged into
a single line)
1, i f q∈FDFA
– A (q) =
0, i f q ∈
/ FDFA
0
– F (q, qL , qR ) = q , defined
0 asfollows:
• (q, qL ∈ Q0 ) → q = q
0
• (q ∈ Q0 ∧ qL ∈ Q\Q0 ) → q = fDFA (qL , si ) , where si is such that q = qsi
Grids of Finite Automata 29
0
• (q ∈ Q0 ∧ qL = ε) → q = fA (q0DFA , si ) , where si is such that q = qsi
0
• for all
other cases, q = ε
– B (w) = qsw1 , qsw2 , . . . , qsw|w| , |w| (w is the input word and w = w1 w2 . . .). In
essence, the i-th component is initialized to a state that corresponds to the i-th sym-
bol of the input, and the very last component is set to be the main one
With the component defined, the task of creating the actual GFA for words of any
given length is trivial. Words of length k are read by Gk = (C, k, f ), where f (i) =
(ε, 2) , i f i = 1
(i − 1, ε) , i f i = k .
(i − 1, i + 1) otherwise
To properly understand how the GFA created in the proof works, one needs to look
at the way the state transition function is defined. The first rule says that a component
that is in a starting state while its left neighbor is in a starting state will remain in the
current state. The second rule says that, if a component is in a starting state matching
some symbol si and its left neighbor is in a non-starting state qDFA j , the current com-
ponent will move to the state that the DFA would go from state qDFA j , given symbol si .
The third rule says that a component that has no working component to the left and is
itself in a starting state qsi will proceed to whatever state the DFA would’ve proceeded
to from the starting state, given symbol si . By following these three rules, the GFA
completely simulates the operation of the DFA on the input word. After a number of
steps equal to the number of components, the last component (the main one) will have
reached a non-starting state, therefore one that matches a state from the DFA. And then
the fourth rule guarantees that the main component, and therefore the entire GFA, halts
and produces output.
With some more thought, it is possible to create GFAs that recognize non-regular
languages as well. For example, the following GFA recognizes the context-free lan-
guage L = {w#wrev | w ∈ Σ∗ ∧ # ∈ / Σ}.
Let us assume Σ = {s1 , s2 , . . . , sy } , # ∈ / Σ. Then the GFA components that can rec-
ognize L are built like this:
– Q = qs1 , qs2 , . . . , qsy , q# , qre ject , qdone , qs1 ,s1 , . . . , qs1 ,sy , . . . , qsy ,s1 , . . . , qsy ,sy
– Q0 = qs1 , qs2 , . . . , qsy , q#
– n = 2 (again, all components arranged in a straight line)
– F (q, qL , qR ) = q0 such that: 0
• (q, qL , qR ∈ Q0 ) → q = q
0
• (∃i ∈ N : q = qsi ∧ (qL = ε ∨ qR = ε)) → q = qsi ,si
0
• ∃i, j, k ∈ N : q = qsi ∧ qL = qs j ,sk ∨ qR = qs j ,sk → q = qsi ,sk
0
• ∃i, j, k, l ∈ N : q = qsi ,s j ∧ qL = qsk ,sl ∨ qR = qsk ,sl → q = qsi ,sl
0
• ∃i, j ∈ N : q = qsi ,s j ∧ (qL = ε ∨ qR = ε) → q = qdone
0
• ∃i, j ∈ N : q = qsi ,s j ∧ (qL = qdone ∨ qR = qdone ) → q = qsi ,si
0
• ∃a, b ∈ N : q = q# ∧ qL = qsa ∧ qR = qsb → q = q#
30 K. Jērin.š
0
• ∃a, b, c ∈ N : q = q# ∧ qL = qsa ,sb ∧ qR = qsc ,sb → q = q#
0
• ∃a, b, c, d ∈ N : q = q# ∧ qL = qsa ,sb ∧ qR = qsc ,sd ∧ b 6= d → q = qre ject
0
• (q = q# ∧ ((qL = ε ∧ qR ∈ Q0 ) ∨ (qL ∈ Q0 ∧ qR = ε))) → q = qre ject
0
• For all other cases, q = ε
1, i f q = q#
– A (q) =
0, i f q 6= q#
– B (w) = q1 , q2 , . . . , q|w| , H , where the i-th component is initialized to a state
(l m
|w|
that corresponds to the i-th input symbol and H = 2 , i f |w| is odd
1, i f |w| is even
Creating the GFA itself is, again, fairly trivial once the component structure is complete.
In fact, the neighbor function f is exactly the same as in the previous proof.
To clarify how this GFA works, one can start by looking at the initialization func-
tion. The intention is to make sure that, for odd word lengths, the main component
is precisely in the middle of the word (even-length words aren’t part of the language
and can automatically be rejected). Next, looking at the answer function shows that the
GFA only accepts the word if the main component terminates from state q# - and a quick
look at the state transitions shows that that state cannot be reached by a component that
wasn’t initialized to that state. All this combined means that the only words that stand
a chance of being accepted are ones where the number of symbols before # and after it
is the same.
In the cases where # is in fact in the middle of the word, the GFA operates by
sending symbols from both ends to the middle. This sending is started by the second
rule for function F – it says that when a component is on one end of the line, it enters
a new state, and its neighbor detects the change and also enters a new state (the meaning
for a state qsi ,s j is that the component was initialized with the symbol si but one of its
neighbors is attempting to send symbol s j to the middle). And a state that has sent its
own symbol proceeds to qdone and then halts. In this way, the main component receives
a pair of symbols from the opposite ends of the line and compares them. If they don’t
match, it goes to qre ject and then halts, rejecting the word. Otherwise, it continues until
everything except the main component has halted. If it is still in q# at that time, the GFA
accepts the word.
This approach of sending symbols allows one to also recognize the context-free
language L = {0n 1n | n > 0}. Again, the main component is placed in the middle of the
word (either the last zero or the first one) for even-length words or in the beginning for
odd-length words. This time the main component must be sent a zero from the left and
a one from the right, otherwise it rejects the word.
Even better results can be accomplished if we don’t limit the component arrange-
ment to a single line. For example, allowing a rectangular placement (and making each
component have four neighbors – top, down, left, right) lets us create a GFA that re-
cognizes the context-sensitive language L = {0n 1n 2n |n > 0}. The GFA that recognizes
it will not be described completely here, but the main idea is to arrange the components
in three rows and use the fact that, for words that belong to the language, the first row
will be initialized to a state corresponding to 0, the second row – to 1, the third row – to
Grids of Finite Automata 31
2. The main component should be placed on the left side of the whole arrangement, and
the components should check if there is a 1 below every 0, a 0 above every 1, a 2 below
every 1 and a 1 above every 2. Should one of these things not hold for any component, it
should enter a state qre ject which would then propagate in all directions until it reached
the main component, which would then halt and reject the word. If this doesn’t happen,
components should halt, one column at a time, from the right. In this situation, the main
component should accept the word when it halts.
A similarly built GFA could also recognize the context-sensitive language
L = {ww | w ∈ Σ∗ }. That GFA would only need two rows of components, and the com-
ponents would have to check if the i-th component of the first row is in the same state
as the i-th component of the second row.
4 Future Work
Obviously, there is still a lot of work to be done in this area. So far we have only
succeeded in placing a lower bound on the computational power of GFAs – they can
recognize all regular languages and some non-regular ones. It is not yet clear whether
all context-free languages, and perhaps even all context-sensitive languages, can be
recognized by GFAs. It is quite likely that the arrangement of components (single line,
rectangle, hexagonal grid, or other options) is also a factor that affects the computational
power.
And, when all of the above is discovered, there is also the question of ”what happens
if the components aren’t deterministic?’ They could be simply non-deterministic, or
probabilistic, or even ultrametric. We expect this to also be a significant factor in this
model’s computational power.
References
1. Holzer, M., Kutrib, M., Malcher, A.: Complexity of multi-head finite automata: Origins and
directions. In: Theoretical Computer Science, vol. 412(1), pp. 83–96 (2011)
2. Buda, A.O.: Multiprocessor automata. In: Information Processing Letters, vol. 25(4),
pp. 257–261 (1987)
3. Cook, M.: Universality in elementary cellular automata. In: Complex Systems, vol. 15(1),
pp. 1–40 (2004)
4. Weisstein, E.W.: Universal Cellular Automaton. From MathWorld–A Wolfram Web Re-
source. http://mathworld.wolfram.com/UniversalCellularAutomaton.html