14
Advance Topics Related to Automata
Introduction
Throughout 13 chapters many topics related to automata are discussed. Those are not the ultimate. Researches are going on in the field of automata like in other fields. In this chapter we shall discuss some new topics related to automata. From these we can accumulate some ideas about the current trend of researches in the field of automata. In this chapter we shall mainly discuss matrix grammar, probabilistic finite automata, cellular automata.
14.1 Matrix Grammar
Matrix grammar is an extension of context free grammar. The difference with CFG is that, here in matrix grammar the production rules are grouped into finite sequences and it is applied in the sequence instead of applying it separately. These sequences are called matrix. The name of the grammar came from this sequence (matrix).
Definition: A matrix grammar is denoted by
where
V_{N} : Set of nonterminals
Σ : Set of terminals
S : Start symbol
M : Finite non empty set of sequence of production rules known as matrices.
It can be written as
Example 14.1
Design a matrix grammar for a^{n}b^{n}c^{n}, n > 0.
Solution: It is already discussed that the grammar is context sensitive. The problem is in designing the productions in such a way that it adds one ‘a’, one ‘b’ and one ‘c’ in each replacement. This is not possible for context free grammar. But if the productions are designed in a group that when ‘a’ and ‘b’ are placed at the same time ‘c’ is also placed, then the problem will be solved.
S → XY is the starting production. Then [X → aXb, Y → cY] are added in a group. It meant when in XY, X is replaced by aXb, at the same time Y will also be replaced by cY. For final replacement make the sequence as [X → ab, Y → c].
Thus the grammar is
where
V_{N} : {S, X, Y}
Σ : {a, b, c}
S : Start symbol
M: [S → XY], [X → aXb, Y → cY], [X → ab, Y → c]
Example 14.2
Design a matrix grammar for L = WW, where W ∈ (a, b)*.
Solution: The length of the string is either 0 or 2n, if  W  = n. For any string ∈ L the i^{th} symbol and the n + i^{th} symbol are same as the string is WW. Already it is discussed that the grammar is not context free. If the start production is S → XY, where X generates first W and Y generates last W, then the problem lies in the number of replacement of X and Y by their corresponding productions. For generating W the productions are
If it can be made confirm that when X will be replaced by a production, Y must be replaced by the same production then the grammar can be constructed. It can only be done using matrix grammar, where we can group the productions as matrices as [X → aX, Y → aY], [X → bX, Y → bY], [X → ε, Y → ε].
Thus the grammar is
where
V_{N} : {S, X, Y}
Σ : {a, b}
S : Start symbol
M : [S → XY], [X → aX, Y → aY], [X → bX, Y → bY], [X → ε, Y → ε]
Example 14.3
Design a matrix grammar for a^{n}b^{n}c^{n}d^{n}, n > 0.
Solution:
where
V_{N} : {S, X, Y}
Σ : {a, b, c, d}
S : Start symbol
M : [S → XY], [X → aXb, Y → cYd], [X → ab, Y → cd]
14.2 Probabilistic Finite Automata
Probabilistic finite automata was first introduced by O. Rabin in 1963. It is an extension of nondeterministic finite automata where the transition functions are assigned to some probability. The transitional function with probability forms a matrix called stochastic matrix. Probabilistic finite automata generalize the concept of Markov model.
Consider the following diagram in Fig. 14.1. Here the number in bracket in each transition represents the probability for the input alphabet. Here we can construct a probability matrix M for each of the alphabets for the state transition.
Fig. 14.1 Probabilistic Finite Automata
Now which is the initial and which is the final state? Probability is also assigned here in two forms:
 Initial State probability (I)
 Final State probability (F)
Let in the previous diagram I(q_{0}) = 1, I(q_{1}) = 0 and F(q_{0}) = 0, F(q_{1}) = 1.
So, the initial state probability I = {1, 0} and final state probability F = {0, 1}.
This is an example of probabilistic automata.
Definition: A probabilistic finite automata is denoted as {Q, Σ, δ, I, F, M} with a probability matrix M with size  Q  ×  Q  for each input alphabet. Here I and F denote the initial and final state probability.
14.2.1 String Accepted by a PA
Let {Q, Σ, δ, I, F, M} be a probabilistic finite automata, η be a real number such that 0 ≤ η ≤ 1 and is the n dimensional column vector whose components are either 0 or 1. The language w is accepted by the probabilistic finite automata on with the intersection point η if (I M(w) ) ≥ η.
The language accepted by probabilistic finite automata is one type of regular language known as stochastic language.
For a finite probabilistic automata the domain of M can be increased by including the following operations.
Example 14.4
Consider the PFA given below.
 Calculate IM(x) , for each x = {ab, ba}.
 Check whether x = {aa and bb} are accepted by the PFA with intersection point η = .5.
Solution:

 x = ab
 x = baa
 x = ab
14.3 Cellular Automata
Cellular automata in short CA was proposed by Ulam and Neumann in 1940 at Los Alamos National Laboratory. This model is used widely in different areas of computer science, mathematics, physics, theoretical biology etc. It is called ‘cellular’ as it consists of regular grid known as cell, where each cell is either ‘0’ or ‘1’. The cells are organized in the form of lattice. The grid may be one dimensional or multi dimensional. For each cell, its surrounding cells (including the cell itself) are called neighbourhood. For a onedimensional array each cell has (2 + 1) neighbour within radius 1. In general for a cell in a onedimensional array has (2r + 1) neighbours where radius is r.
In this section we shall mainly discuss about onedimensional cellular automata.
CA evolves in discrete space and time, and can be viewed as an autonomous finite state machine (FSM). Each cell stores a discrete variable at time that refers to the present state (PS) of the cell. The next state (NS) of the cell at (t + 1) is affected by its state and the states of its neighbours at time t.
Definition: A cellular automata (CA) is a collection of cells arranged in the form of lattice, such that each cell changes state as a function of time according to a defined set of rules that includes the states of neighbouring cells.
14.3.1 Characteristics of Cellular Automata
 It performs synchronous computation.
 Each cell can be in any finite number of state.
 Neighbourhood describes how the cells are connected with its surrounding cells.
 Update rule computes the change in the state of a cell based on the states of its neighbours. State of a cell at t_{i + 1} is dependent on the states of its neighbourhood cell at t_{i}.
Let us consider a onedimensional CA. There are 256 rules [From 0 to 255] are defined for updatation.
Update Rule: A 3neighbourhood CA (self, left and right neighbours), where a CA cell is having two states −0 or 1 and the next state of i^{th} CA cell is
where are the present states of the left neighbour, self and right neighbor of the i^{th} cell at time t and f_{i} is the next state function. The states of the cells at t is the present state of the CA. Therefore, the next state of the ncell CA is
Rules can be constructed in two ways—warp around or by null stuffing. In wrap around the sequence is considered as circular as given in Fig. 14.2(a).
Fig. 14.2 (a) Wrap Around
In null stuffing ‘0’ is stuffed at both sides of the original sequence. This is described in Fig. 14.2(b).
Fig. 14.2 (b) Null Stuffed
Let us consider the value as 210 (< 256). The binary equivalent of 210 is 11010010. Consider a onedimensional cellular automata. Now construct the rules for it.
The cell representations of 111 and 010 is given below.
Now take a sequence 1001. Let us construct the sequence to t_{3} using wrap around and null stuffing technique.
Wrap Around
The cells representation are given below
Null Stuffed: In null stuffed two ‘0’ are added at both sides of the original string.
The cells representation are given below
Example 14.5
Find the update of a onedimensional CA rules for 212.
Solution: The binary equivalent of 212 is 11010100.
The rules are
14.3.2 Applications of Cellular Automata
Cellular automata is not only used in Computer Science field, it also has different applications in other fields.
In the Field of Computer Science
 Cryptography
 Detecting fault tolerance in digital circuit
 Simulation of complex system
Beyond the Field of Computer Science
 Simulation of gas behavior
 Simulation of forest fire propagation
 Simulation of bone erosion.
Cellular automata are used to identify fault in some digital circuits.
Let consider an OR gate
Its truth table is
X  Y  O/P 

0  0 
0 
0  1  1 
1  0  1 
1  1  1 
It may happen that the input Y is faulty. It takes ‘1’ for any input applied to it. Thus the output that we get will always be ‘1’. This is called ‘Struck at 1’. Similarly the problem ‘Struck at 0’ can occur for a digital circuit.
Rule 192: Binary of 192 is 11000000
The rule is
Let the initial sequence is 1111.
By null stuffing at both sides the sequence become 011110.
So
Let it t_{0} the bits are labeled as S_{0}, S_{1}, S _{2}……. S_{5}.
State S_{1} in t_{1} depends on S_{0}, S_{1} and S_{2} of t_{0}. The bit pattern is 011, so the value of S_{1} in t_{1} is 0 (according to rule 192). By the same way all the other bits are placed. By the same way the patterns for t_{2} and t_{3} are generated.
Let a digital circuit has four inputs. To identify the ‘Struck at 0’ problem all bits are taken as ‘1’ and patterns are generated for next (n–1) steps, where n is the number of input line. If the LSB is other than ‘1’ in t_{n–1} step then we can say that the circuit is faulty.