Chapter 14: Advance Topics Related to Automata – Introduction to Automata Theory, Formal Languages and Computation

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

 

G = {VN, Σ, M, S}

 

where

    VN : Set of non-terminals

      Σ : 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 anbncn, 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

 

G = {VN, Σ, M, S}

 

where

VN : {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 ith symbol and the n + ith 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

 

S → aS | bS | ε

 

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

 

G = {VN, Σ, M, S}

 

where

VN : {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 anbncndn, n > 0.

Solution:

 

G = {VN, Σ, M, S}

 

where

VN : {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 non-deterministic 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:

  1. Initial State probability (I)
  2. Final State probability (F)

Let in the previous diagram I(q0) = 1, I(q1) = 0 and F(q0) = 0, F(q1) = 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.

  1. Calculate IM(x) , for each x = {ab, ba}.
  2. Check whether x = {aa and bb} are accepted by the PFA with intersection point η = .5.

Solution:

    1. x = ab
    2. x = baa
    1. x = aa

      As .625 > .5, thus x = aa is accepted by the PFA on intersection point .5.

    2. x = bb

      As .325 < .5, thus x = bb is not accepted by the PFA on intersection point .5.

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 one-dimensional array each cell has (2 + 1) neighbour within radius 1. In general for a cell in a one-dimensional array has (2r + 1) neighbours where radius is r.

In this section we shall mainly discuss about one-dimensional 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 ti + 1 is dependent on the states of its neighbourhood cell at ti.

Let us consider a one-dimensional CA. There are 256 rules [From 0 to 255] are defined for updatation.

Update Rule: A 3-neighbourhood CA (self, left and right neighbours), where a CA cell is having two states −0 or 1 and the next state of ith CA cell is

where are the present states of the left neighbour, self and right neighbor of the ith cell at time t and fi 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 n-cell 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 one-dimensional 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 t3 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 one-dimensional 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 t0 the bits are labeled as S0, S1, S 2……. S5.

State S1 in t1 depends on S0, S1 and S2 of t0. The bit pattern is 011, so the value of S1 in t1 is 0 (according to rule 192). By the same way all the other bits are placed. By the same way the patterns for t2 and t3 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 tn–1 step then we can say that the circuit is faulty.