Two-Dimensional Input-Revolving Automata

Abstract

A new type of two-dimensional automaton for accepting two-dimensional languages, called as two-dimensional input-revolving automaton is introduced in this paper. It is an extension of input-revolving automaton for string languages. We bring out all the variants of this automaton which are based on the various types of column-revolving operations considered here. We compare the families of array languages accepted by the variants of these automata along with the well known families of Siromoney matrix languages. We discuss some of the closure properties of the new families of array languages and give an application in steganography.

1 Introduction

Two-dimensional languages, also called picture languages, are sets of two-dimensional arrays of symbols chosen from a finite alphabet. Their application and importance can be seen in image processing, pattern recognition, character recognition and also in studies concerning cellular automaton and other models of computing. Due to the structure handling ability of the syntactic models, syntactic techniques of generation of digital picture arrays have become one of the major areas of theoretical studies in picture analysis and pattern recognition. Various grammars and automata have already been proposed for the generation and recognition of rectangular picture languages [4, 8,9,10,11, 13, 14, 16].

Automata play a vital role in the theory of picture recognizability. The generalization of finite state automata to two-dimensional languages can be attributed to Blum and Hewitt [2] who introduced the notion of 4-way automata. Array automata acting on scenes (two-dimensional tapes) are defined in [5]. Motivated by certain floor designs called “Kolam” patterns, Siromoney et al. [12] introduced Siromoney Matrix Grammars (SMG), a simple and elegant grammar model for generating rectangular arrays. Several variations of Siromoney matrix grammars have already been added to the literature, for instance [15, 17].

In this paper, we extend the concept of input-revolving automata systematically investigated in [1], with several shift operations, namely left-revolving, right-revolving and circular-interchanging operations to two dimensional languages. Input-revolving automata work similar to ordinary finite automata except that they can make three special shift operations as mentioned. Two-dimensional input-revolving automata work on an input array row by row and every row computation is same as that of input-revolving automata for string languages. Here we introduce column shift transitions, namely left column-revolving, right-column revolving and circular column-interchanging transitions which shifts an entire column. We study all the variants of these automata, both deterministic and non-deterministic, based on the various types of column-revolving operations considered. We compare various classes of languages accepted by these automata with the families of Siromoney matrix languages [12].

2 Preliminaries

In this section we recall some notions related to formal language theory and array grammars (see [7, 12]). Let $\varSigma$ be a finite alphabet, $\varSigma ^*$ is the set of words over $\varSigma$ including the empty word $\lambda$. $\varSigma ^+=\varSigma ^*-\{\lambda \}$. For $w\in \varSigma ^*$ and $a\in \varSigma$, $|w|_a$ denotes the number of occurrences of a in w. An array consists of finitely many symbols from $\varSigma$ that are arranged as rows and columns in some particular order and is written in the form, $A = \begin{bmatrix} a_{11}&\cdots&a_{1n}\\ \vdots&\ddots&\vdots \\ a_{m1}&\cdots&a_{mn} \end{bmatrix}$ or in short $A = [a_{ij}]_{m\times n}$, for all $a_{ij}\in \varSigma$, $i=1,2,\ldots ,m$ and $j=1,2,\ldots ,n$. The set of all arrays over $\varSigma$ is denoted by $\varSigma ^{**}$ which also includes the empty array $\varLambda$ (zero rows and zero columns). $\varSigma ^{++} = \varSigma ^{**}-\{\varLambda \}$. For $a\in \varSigma$, $|A|_a$ denotes the number of occurrences of a in A. The column concatenation of ${A} = \begin{bmatrix} a_{11}&\cdots&a_{1p}\\ \vdots&\ddots&\vdots \\ a_{m1}&\cdots&a_{mp} \end{bmatrix}$, and $B = \begin{bmatrix} b_{11}&\cdots&b_{1q}\\ \vdots&\ddots&\vdots \\ b_{n1}&\cdots&b_{nq} \end{bmatrix}$, defined only when $m=n$, is given by . As $1\times n$-dimensional arrays can be easily interpreted as words of length n (and vice versa), we will then write their column catenation by juxtaposition (as usual). Similarly, the row concatenation, defined only when $p=q$, is given by $A \ominus B = \begin{bmatrix} a_{11}&\cdots&a_{1p}\\ \vdots&\ddots&\vdots \\ a_{m1}&\cdots&a_{mp}\\ b_{11}&\cdots&b_{1q}\\ \vdots&\ddots&\vdots \\ b_{n1}&\cdots&b_{nq} \end{bmatrix}$. The empty array acts as the identity for column and row catenation of arrays of arbitrary dimensions. If $A = \begin{bmatrix} a_{11}&\cdots&a_{1n}\\ \vdots&\ddots&\vdots \\ a_{m1}&\cdots&a_{mn} \end{bmatrix}$, then the transpose of A is $A^T = \begin{bmatrix} a_{11}&\cdots&a_{m1}\\ \vdots&\ddots&\vdots \\ a_{1n}&\cdots&a_{mn} \end{bmatrix}$.

Given a picture $A\in \varSigma ^{**}$ of size (m, n), we define $\hat{A}$ as the picture of size $(m,n+1)$ obtained by adjoining a special symbol $\#\notin \varSigma$ to the right end of the input array. $|A|_c$ is the number of columns in picture A and $|A|_r$ is the number of rows in picture A. If every element in an $m\times n$ array is a, then we write this array as $a^n_m$.

Definition 1

A Context-sensitive matrix grammar (CSMG) (Context-free matrix grammar (CFMG), Right-linear matrix grammar (RLMG)) is defined by a 7-tuple $G = (V_h, V_v, \varSigma _I, \varSigma , S, R_h, R_v)$, where: $V_h$ is a finite set of horizontal nonterminals; $V_v$ is a finite set of vertical nonterminals; $\varSigma _I \subseteq V_v$ is a finite set of intermediates; $\varSigma$ is a finite set of terminals; $S \in V_h$ is a starting symbol; $R_h$ is a finite set of horizontal context-sensitive (context-free, right-linear) rules; $R_v$ is a finite set of vertical right-linear rules.

There are two phases of derivation of the Siromoney Matrix Grammars. In the first phase, a horizontal string of intermediate symbols is generated by means of any type of Chomsky grammar rules in $R_h$. During the second phase treating each intermediate as a start symbol, vertical generation of the actual picture is done parallely, by applying $R_v$. Parallel application ensures that the terminating rules are all applied simultaneously in every column and that the column grows only in downward direction. The language generated by a CSMG (CFMG, RLG) is called a CSML (CFML, RML). For more information, we can refer to [12]. We denote the family of Siromoney matrix languages by $\mathfrak {L}$(X), where $X\in \{CSML,CFML,RML\}$.

3 Two-Dimensional Input-Revolving Finite Automata

In this section we introduce the two-dimensional input-revolving finite automaton and explain its working with an example.

Definition 2

A two-dimensional non-deterministic column revolving finite automaton, a 2-NCRFA for short, is a 6-tuple $M=(Q,\varSigma ,\delta ,\varDelta ,q_0,F)$, where Q is a finite set of states, $\varSigma$ is an input alphabet, $Q\cap \varSigma =\emptyset$, $\delta \subseteq Q\times (\varSigma \cup \{\lambda ,\#\})\times 2^Q$ is the finite set of transition rules, $\#$ is a special symbol not in $Q\cup \varSigma$, $\varDelta \subseteq Q\times (\varSigma \cup \{\lambda \})\times 2^Q$ is the finite set of column revolving rules, $q_0\in Q$ is the initial state, and F is the set of final states.

M is said to be $\lambda$-free if $\delta$ is a mapping from $Q\times (\varSigma \cup \{\#\})$ to $2^Q$ and $\varDelta$ is a mapping from $Q\times \varSigma$ to $2^Q$.

Members of $\delta , \varDelta$ are referred to as the rules of M and instead of $(p,y,q)\in \delta$ (or $\varDelta$), we write $py\rightarrow q \in \delta$ (or $\varDelta$). Based on the different interpretations of the mapping $\varDelta$, we formally distinguish the different operations on the input array and hence categorize various types of 2-NCRFA. For this, we consider configurations of this automaton for some input array $A= \begin{array}{c} X\\ uv\\ Z \end{array}$, of size $m\times n$ with $X,Z,u,v\in \varSigma ^{**}$ , uv is $1\times n$ array, to be of the form $\begin{array}{c} X\\ uqv\\ Z\\ \end{array}$ where $q\in Q$. This means that q is the current state of the finite control with tape head reading the first element in v. (X, u) and (v, Z) are therefore the read and unread part of the input array, respectively. The transition of a configuration to next configuration can be induced by either $\delta$ or $\varDelta$.

• 1. Let $a\in \varSigma \cup \{\lambda \}$ and $A= \begin{array}{c} X\\ uav\\ Z \end{array}$ be an $m\times n$ array in $\varSigma ^{**}$ with $|X|_c=|uav|_c=|Z|_c$. If $qa\rightarrow p$ is in $\delta$ then, $\begin{array}{c} \hat{X}\\ uqav\#\\ \hat{Z}\\ \end{array}\vdash _M \begin{array}{c} \hat{X}\\ uapv\#\\ \hat{Z}\\ \end{array}$. These transitions are called as the normal transitions. Let $A= \begin{array}{c} X\\ u\\ Z \end{array}$ be a $m\times n$ array in $\varSigma ^{**}$ with $|X|_c=|u|_c=|Z|_c, u$ is a $1\times n$ array. If $q\#\rightarrow p$ is in $\delta$ then, $\begin{array}{cc} \hat{X}&{} \\ u&{}q\#\\ \hat{Z}&{} \\ \end{array}\vdash _M \begin{array}{c} \hat{X'}\\ pu'\#\\ \hat{Z'}\\ \end{array}$, where, $X'= \begin{array}{c} X\\ u \end{array}, Z= \begin{array}{c}u'\\ Z' \end{array}$ and $u'$ is a $1\times n$ array.

• 2. Column revolving operations are performed by applying the rules from $\varDelta$. For $a\in \varSigma \cup \{\lambda \}, b\in \varSigma$, a $m\times n$ array, $A= \begin{array}{cccc} X_1&{}X_2&{}X_3&{}X_4\\ u&{}a&{}v&{}b\\ Z_1&{}Z_2&{}Z_3&{}Z_4 \end{array}$ in $\varSigma ^{**}$ with $|X_1|_c=|u|_c=|Z_1|_c, |X_3|_c=|v|_c=|Z_3|_c, |X_2|_c=|Z_2|_c=|X_4|_c=|Z_4|_c=1$ and a rule $qa\rightarrow p$ in $\varDelta$,

  • (a) a left column-revolving transition is defined by

    $$\begin{aligned} \begin{array}{|cccccc|}\hline X_1&{}&{}X_2&{}X_3&{}\mathbf {X_4}&{}\#\\ u&{}q&{}a&{}v&{}\mathbf {b}&{}\#\\ Z_1&{}&{}Z_2&{}Z_3&{}\mathbf {Z_4}&{}\#\\ \hline \end{array}\vdash _M \begin{array}{|cccccc|}\hline X_1&{}&{}\mathbf {X_4}&{}X_2&{}X_3&{}\#\\ u&{}q&{}\mathbf {b}&{}a&{}v&{}\#\\ Z_1&{}&{}\mathbf {Z_4}&{}Z_2&{}Z_3&{}\#\\ \hline \end{array} \end{aligned}$$

  • (b) a right column-revolving transition is defined by

    $$\begin{aligned} \begin{array}{|cccccc|}\hline X_1&{}&{}\mathbf {X_2}&{}X_3&{}X_4&{}\#\\ u&{}q&{}\mathbf {a}&{}v&{}b&{}\#\\ Z_1&{}&{}\mathbf {Z_2}&{}Z_3&{}Z_4&{}\#\\ \hline \end{array}\vdash _M \begin{array}{|cccccc|}\hline X_1&{}&{}X_3&{}X_4&{}\mathbf {X_2}&{}\#\\ u&{}q&{}v&{}b&{}\mathbf {a}&{}\#\\ Z_1&{}&{}Z_3&{}Z_4&{}\mathbf {Z_2}&{}\#\\ \hline \end{array} \end{aligned}$$

  • (c) a circular column-interchanging transition is defined by

    $$\begin{aligned} \begin{array}{|cccccc|}\hline X_1&{}&{}\mathbf {X_2}&{}X_3&{}\mathbf {X_4}&{}\#\\ u&{}q&{}\mathbf {a}&{}v&{}\mathbf {b}&{}\#\\ Z_1&{}&{}\mathbf {Z_2}&{}Z_3&{}\mathbf {Z_4}&{}\#\\ \hline \end{array}\vdash _M \begin{array}{|cccccc|}\hline X_1&{}&{}\mathbf {X_4}&{}X_3&{}\mathbf {X_2}&{}\#\\ u&{}q&{}\mathbf {b}&{}v&{}\mathbf {a}&{}\#\\ Z_1&{}&{}\mathbf {Z_4}&{}Z_3&{}\mathbf {Z_2}&{}\#\\ \hline \end{array} \end{aligned}$$

  If $a=\lambda$, then the column-revolving operation is carried out irrespective of what symbol is being read by the finite state control. If ‘a’ is being read by the state q at the end of some row of the input array then there is no column-revolving involved and simply the state will be changed to p.

Whenever there is a choice between a normal transition or a column-revolving transition, the next move is non-deterministically chosen by the automaton. A deterministic 2-dimensional column revolving automaton, a 2-DCRFA for short is defined in the same way as 2-NCRFA except that $\delta \subseteq Q\times (\varSigma \cup \{\lambda ,\#\})\times Q$, $\varDelta \subseteq Q\times (\varSigma \cup \{\lambda \})\times Q$ and for which there is at most one choice for any possible configuration.

The reflexive transitive closure of $\vdash _M$ is denoted by, $\vdash _M^*$.

Based on the column-revolving operation involved, a 2-NCRFA is referred to as two-dimensional non-deterministic left-column revolving (2-NLCRA), right column-revolving (2-NRCRA) or circular column-interchanging finite automaton (2-NCIRA). The corresponding deterministic variants are referred to as 2-DLCRA, 2-DRCRA and 2-DCIRA. We can also consider bi-column-revolving automaton, where both left column-revolving and right column-revolving transitions are involved. We can formally define this two-dimensional non-deterministic bi-column-revolving automaton or in short 2-NBCRA to be a 7-tuple, $M=(Q,\varSigma ,\delta ,\varDelta _l,\varDelta _r,q_0,F)$, where $M=(Q,\varSigma ,\delta ,\varDelta _l,q_0,F)$ is a 2-NLCRA and $M=(Q,\varSigma ,\delta ,\varDelta _r,q_0,F)$ is a 2-NRCRA. Whenever we refer to an automaton as two-dimensional input-revolving finite automaton it is either left column-revolving, right column-revolving, bi-column-revolving or circular column interchanging.

We define the language accepted by a two-dimensional input-revolving finite automaton M to be,

$$\begin{aligned} L(M)=\left\{ A= \begin{array}{c} A_1\\ \vdots \\ A_m \end{array} \in \varSigma ^{**} \;\Bigg |\; \begin{array}{c} q_0A_1\\ \vdots \\ A_m \end{array} \vdash _M^* \begin{array}{c} A_1\\ \vdots \\ A_m\\ q\lambda \end{array} \text { or simply } \begin{array}{c} q_0A_1\\ \vdots \\ A_m \end{array} \vdash _M^* q \text { with } q\in F\right\} . \end{aligned}$$

We denote the family of languages accepted by devices of type X by $\mathfrak {L}$(X).

Example 1

Let,

$M=(\{q_0,q_1,q_2\},\{0,1,2\},\delta ,\varDelta ,q_0,\{q_0\})$ be a 2-DCRFA, where $\delta =\{q_00\rightarrow q_1, q_11\rightarrow q_2, q_22\rightarrow q_0, q_0\#\rightarrow q_0\}$ and $\varDelta =\{q_01\rightarrow q_0, q_02\rightarrow q_0, q_10\rightarrow q_1, q_12\rightarrow q_1, q_20\rightarrow q_2, q_21\rightarrow q_2\}$.

The automaton M accepts the following language regarded as either 2-DLCRA or 2-DRCRA,

$$ L(M)=\left\{ X= \begin{array}{c} X_1\\ \vdots \\ X_m \end{array} \in \{0,1,2\}^{**} \Bigg | \begin{array}{c} \text {each}\, X_i\text {'}\mathrm{s} \, \text {are of size } 1\times n \text { and }\\ |X_i|_0=|X_i|_1=|X_i|_2, \forall \quad i=1,2,\ldots ,m \end{array} \right\} $$

Working:

The automaton works on $\hat{X}$ if X is given as the input array. Starting from state $q_0$ and the tape head on the first element of the first row in the input X, the automaton M tries to read 0, 1 and 2 sequentially beginning with 0. It uses the $\delta$ transitions to store the current missing symbol in its finite control in order to search for it. Being in a search state, all non-matching symbol are column-wise shifted by the transitions from $\varDelta$. If the automaton reads $\#$, it means that a complete row is read. Now the automaton uses the rule $q_0\#\rightarrow q_0$ in $\delta$ and moves to the first element of the very next row. This computational process is repeated for the subsequent rows until the entire array is read. If after reading the entire row, the automaton is in state $q_0$, then the input array is accepted or else it is rejected. Thus accepted array has equal number of 0s, 1s and 2s in each of its rows.

Example 2

The language $L=\{(\bullet ^n X \bullet ^n)_m \mid n,m>0\}$ is accepted by a 2-DLCRA, $M= (Q,\{\bullet ,X\},\delta ,\varDelta ,q_0,\{q_4\})$, where $Q=\{q_0,q_1,q_2,q_3,q_4,q_5\}$, $\delta =\{q_1 \bullet \rightarrow q_2, q_2 \bullet \rightarrow q_0, q_0 X\rightarrow q_3, q_3 \#\rightarrow q_4, q_4 \bullet \rightarrow q_5, q_5 \bullet \rightarrow q_4, q_4 X\rightarrow q_3\}$ and $\varDelta =\{q_0 \bullet \rightarrow q_1\}$. The working of this automaton for an input array $\begin{array}{lllll} \bullet &{}\bullet &{}X&{}\bullet &{}\bullet \\ \bullet &{}\bullet &{}X&{}\bullet &{}\bullet \\ \bullet &{}\bullet &{}X&{}\bullet &{}\bullet \\ \bullet &{}\bullet &{}X&{}\bullet &{}\bullet \\ \end{array}$ is given as follows (Successive configurations are listed one below the other. The configuration at the end of a column is succeeded by the configuration at the top of the next column. The last configuration at the last column of this page is succeeded by the first configuration on the first column of the next page):

The definition of two-dimensional column revolving finite automaton allows $\lambda$-transitions of both $\delta$ and $\varDelta$. The $\lambda$ moves do not increase the computational power of any such automaton. (It is so, because, for every non-deterministic column-revolving automaton involving $\lambda$ transitions in normal rules or column-revolving rules, an equivalent $\lambda$-free non-deterministic column-revolving automaton can be easily constructed (same for the deterministic variants)).

4 Comparison of the Variants

In this section we consider two-dimensional deterministic and non-deterministic variants of the column-revolving finite automata in a detailed way. In particular, we give the comparison among the different column-revolving rules and it turns out that the non-deterministic variants are better than the deterministic ones.

Theorem 1

The language $L=\{(\bullet ^n X \bullet ^n)_m \mid n,m>0\}$ is not accepted by any 2-NRCRA.

Proof

We assume that the language L is accepted by some 2-NRCRA, $M=(Q,\varSigma , \delta , \varDelta ,q_0, F)$ with $|Q|=t$. Let us consider an array A with $|A|_c>2t$, which is given as an input to the automaton M. The automaton begins its computation starting from the first element of the first row. During its computation on the first row some state, say p, appears at least twice, because of Pigeon Hole Principle. Let us consider that the first appearance of state p is reached after i ordinary moves and j right column-revolving moves with $0\le j < t$. Therefore we have,

$$\begin{aligned} \begin{array}{crcccl} q_0&{}\bullet &{}\bullet ^{n-1}&{}X&{}\bullet ^n&{}\#\\ (&{}\bullet &{}\bullet ^{n-1}&{}X&{}\bullet ^n&{}\#)_{m-1}\\ \end{array}\vdash _M^* \begin{array}{rllllll} \bullet ^i&{}p&{}\bullet &{}\bullet ^{n-1-i-j}&{}X&{}\bullet ^{n+j}&{}\#\\ (\bullet ^i&{}&{}\bullet &{}\bullet ^{n-1-i-j}&{}X&{}\bullet ^{n+j}&{}\#)_{m-1}\\ \end{array} \end{aligned}$$

Let us consider that the second appearance of state p is reached after k ordinary moves and l right column-revolving moves with $1\le l < t-j$. Therefore we have,

$$\begin{aligned} \begin{array}{rllllll} \bullet ^i&{}p&{}\bullet &{}\bullet ^{n-1-i-j}&{}X&{}\bullet ^{n+j}&{}\#\\ (\bullet ^i&{}&{}\bullet &{}\bullet ^{n-1-i-j}&{}X&{}\bullet ^{n+j}&{}\#)_{m-1}\\ \end{array}\vdash _M^* \begin{array}{rllllll} \bullet ^{i+k}&{}p&{}\bullet &{}\bullet ^{n-1-i-j-k-l}&{}X&{}\bullet ^{n+j+l}&{}\#\\ (\bullet ^{i+k}&{}&{}\bullet &{}\bullet ^{n-1-i-j-k-l}&{}X&{}\bullet ^{n+j+l}&{}\#)_{m-1}\\ \end{array} \end{aligned}$$

Since we have assumed that the array A is accepted, the computation reaches an accepting state, say $q_f$, such that,

$$\begin{aligned} \begin{array}{rllllll} \bullet ^{i+k}&{}p&{}\bullet &{}\bullet ^{n-1-i-j-k-l}&{}X&{}\bullet ^{n+j+l}&{}\#\\ (\bullet ^{i+k}&{}&{}\bullet &{}\bullet ^{n-1-i-j-k-l}&{}X&{}\bullet ^{n+j+l}&{}\#)_{m-1}\\ \end{array}\vdash _M^* \begin{array}{crl} q_f\\ \end{array} \end{aligned}$$

When we consider the input array as $A'=(\bullet ^{n-k-l}X\bullet ^{n+l})_m$, the automaton accepts this input too,

$$\begin{aligned} \begin{array}{rllllll} q_0&{}\bullet &{}\bullet ^{n-1-k-l}&{}X&{}\bullet ^{n+l}&{}\#\\ (&{}\bullet &{}\bullet ^{n-1-k-l}&{}X&{}\bullet ^{n+l}&{}\#)_{m-1}\\ \end{array}\vdash _M^* \begin{array}{rllllll} \bullet ^{i}&{}p&{}\bullet &{}\bullet ^{n-1-i-j-k-l}&{}X&{}\bullet ^{n+j+l}&{}\#\\ (\bullet ^{i}&{}&{}\bullet &{}\bullet ^{n-1-i-j-k-l}&{}X&{}\bullet ^{n+j+l}&{}\#)_{m-1}\\ \end{array}\vdash _M^* \begin{array}{crl} q_f\\ \end{array} \end{aligned}$$

But the array $A'$ is not a member of the language L. This is a contradiction to the initial assumption. Hence the theorem is proved.   $\square$

Theorem 2

Let $L=\{\{0,1\}^{**} | \exists$ at least one row in which number of 0s and 1s are not equal$\}$. This language is not accepted by any 2-DBCRA but is accepted by some 2-NRCRA.

Proof

We first prove that the language L is not accepted by any 2-DBCRA, by the method of contradiction. Let us assume that the language is accepted by some 2-DBCRA, $M=(Q,\varSigma , \delta , \varDelta ,q_0, F)$ with $|Q|=t$. Let $A=(0^n1^{2n-j}0^n)_m$ with $n,m,j>2$, $j<n$, $j\ne 0$ and $n>t$ be the input given to the automaton. Based on pigeon hole principle, there exists a state, say p, which appears at least twice during the computation on first row. Let the first occurrence of state p be reached after: i normal transition, $l_1$ left column-revolving transition and $r_1$ right column-revolving transition,

$$\begin{aligned} \begin{array}{crcccl} q_0&{}0&{}0^{n-1}&{}1^{2n-j}&{}0^n&{}\#\\ (&{}0&{}0^{n-1}&{}1^{2n-j}&{}0^n&{}\#)_{m-1}\\ \end{array}\vdash _M^* \begin{array}{rllllll} 0^i&{}p&{}0&{}0^{n-1-i+l_1-r_1}&{}1^{2n-j}&{}0^{n-l_1+r_1}&{}\#\\ (0^i&{}&{}0&{}0^{n-1-i+l_1-r_1}&{}1^{2n-j}&{}0^{n-l_1+r_1}&{}\#)_{m-1}\\ \end{array} \end{aligned}$$

Let the second occurrence of state p be reached after: j normal transition, $l_2$ left column-revolving transition and $r_2$ right column-revolving transition.

Since the considered array A is in the language L, the computation reaches the accepting state, say $q_f$ i.e.,

$$\begin{aligned} \begin{array}{rllllll} 0^{i+j}&{}p&{}0&{}0^{n-1-i-j+l_1-r_1+l_2-r_2}&{}1^{2n-j}&{}0^{n-l_1+r_1-l_2+r_2}&{}\#\\ (0^{i+j}&{}&{}0&{}0^{n-1-i-j+l_1-r_1+l_2-r_2}&{}1^{2n-j}&{}0^{n-l_1+r_1-l_2+r_2}&{}\#)_{m-1}\\ \end{array}\vdash _M^* \ q_f \end{aligned}$$

Let us now consider the input array $A'=(0^{n-j+l_2-r_2}1^{2n-j}0^{n-l_2+r_2})_m$. Due to the deterministic behavior, the computation on the input array $A'$ is,

But this is a contradiction because $A'$ is not in L. Now we prove that there is a 2-NRCRA, $M'$, that accepts the language L. $M'$ works on each row by reading a 0 and a 1 alternatively. This part is similar to the working of the automaton considered in Example 1. The input array is rejected if $M'$ finds that the numbers are equal in each and every row. If there is at least one row in which the numbers are not equal then $M'$ accepts the input array. Also, during the computation on each and every row, $M'$ guesses whether there are only 0’s or 1’s remaining on present row and if that is the case then it simply reads the remaining elements on the row and the guess is verified. Hence, $M'$ can accept the input array for correct guess on at least one row or else reject it. Hence the proof.   $\square$

Theorem 3

There is a language L not accepted by any 2-NLCRA but accepted by some 2-DRCRA.

Proof

To prove this theorem, we consider the following language $L=$

Let us assume that L is accepted by some 2-NLCRA, $M=(Q,\varSigma , \delta , \varDelta ,q_0, F)$ with $|Q|=t$. Let us consider the array $A=(0^{n+1}1^{2n}0^n)_m$ with $n,m>0$ and $n>t$ to be the input given to the automaton. Based on assumption, there is an accepting computation such that a state, say p appears at least twice during the computation on first row. Let the first occurrence of state p be reached after i normal transition and j left column-revolving transition and its second appearance be reached after k normal transition and l left column-revolving transition with $0\le i,j,k,l\le n$ and $k+l>0$. Hence we have,

Let us consider the computation of M for the input array $A'=(0^{n+1-k+l}1^{2n}0^{n-l})$,

$$\begin{aligned} \begin{array}{rllllll} q_0&{}0&{}0^{n-k+l}&{}1^{2n}&{}0^{n-l}&{}\#\\ (&{}0&{}0^{n-k+l}&{}1^{2n}&{}0^{n-l}&{}\#)_{m-1}\\ \end{array}\vdash _M^* \begin{array}{rllllll} 0^{i}&{}p&{}0&{}0^{n-i+j-k+l}&{}1^{2n}&{}0^{n-j-l}&{}\#\\ (0^{i}&{}&{}0&{}0^{n-i+j-k+l}&{}1^{2n}&{}0^{n-j-l}&{}\#)_{m-1}\\ \end{array}\vdash _M^* \ q_f \end{aligned}$$

But this implies that $A'\in L$. Since, $n+\frac{l-k}{2}+n-l=2n-\frac{l+k}{2}\ne 2n$ implies $A'\notin L$, we arrive at a contradiction.

The 2-DRCRA, $M=(\{q_0,q_1,q_2,q_3,q_4\},\{0,1\},\delta ,\varDelta ,q_0,\{q_4\})$, where $\delta =\{q_00\rightarrow q_1, q_11\rightarrow q_2, q_20\rightarrow q_3, q_31\rightarrow q_2, q_3\#\rightarrow q_4, q_40\rightarrow q_3\}$ and $\varDelta =\{q_10\rightarrow q_1, q_21\rightarrow q_2, q_30\rightarrow q_3\}$ accepts the language L.

Theorem 4

• (i) The family $\mathfrak {L}$(2-DLCRA) is properly included in $\mathfrak {L}$(2-NLCRA)

• (ii) The family $\mathfrak {L}$(2-DRCRA) is properly included in $\mathfrak {L}$(2-NRCRA)

• (iii) The family $\mathfrak {L}$(2-DBCRA) is properly included in $\mathfrak {L}$(2-NBCRA)

• (iv) The family $\mathfrak {L}$(2-DRCRA) is properly included in $\mathfrak {L}$(2-DBCRA)

• (v) The family $\mathfrak {L}$(2-NRCRA) is properly included in $\mathfrak {L}$(2-NBCRA)

• (vi) The family $\mathfrak {L}$(2-DLCRA) is properly included in $\mathfrak {L}$(2-DBCRA)

• (vii) The family $\mathfrak {L}$(2-NLCRA) is properly included in $\mathfrak {L}$(2-NBCRA)

Proof

All inclusions are trivial. From Theorem 1, $\exists$ a language not accepted by any 2-NRCRA and hence also by any 2-DRCRA. But, as seen in Example 2 it is accepted by some 2-DLCRA and hence by some 2-DBCRA and 2-NBCRA. This proves (iv) and (v). By Theorem 2, $\exists$ a language not accepted by any 2-DBCRA and hence by any 2-DLCRA, 2-DRCRA but is accepted by 2-NRCRA, and hence by some 2-NBCRA. This proves (ii) and (iii). By Theorem 3 $\exists$ a language not accepted by any 2-NLCRA and hence by any 2-DLCRA but is accepted by some 2-DRCRA and hence by 2-DBCRA and 2-NBCRA. This proves (vi) and (vii).

To prove strict inclusion of (i), we consider the language L from Example 2. Let , where . Clearly $L'$ is accepted by some 2-NLCRA. But $L'$ is not accepted by any 2-DLCRA. We prove this by contradiction. Let us assume that there is a 2-DLCRA, $M=(Q,\varSigma , \delta , \varDelta ,q_0, F)$ with $|Q|=t$. We consider an input array $A=(\bullet ^{2n}X\bullet ^{2n}Y^n\bullet ^{2n})_m \in L'$ with $n>t$. During the computation on the first row some state, say $p\in Q$ appears at least twice due to our choice of n, let the first appearance be after i normal moves and j left column-revolving moves and the second appearance be after k normal moves and l left column-revolving moves, with $0\le i,j,k,l\le n$, $k+l>0$. Since M is deterministic we have,

We find that there exists an accepting configuration for the input array $A'=(\bullet ^{2n-k+l}X\bullet ^{2n}Y^n\bullet ^{2n-l})_m$ such that,

But this implies that $k=l$. Since $l+k>0$, we derive at $l>0$. Since, M is deterministic, the accepting computation for the input array $A''=(\bullet ^{2n}X\bullet ^{2n})_m$ is,

where $q_f'\in Q$. We can also obtain an accepting configuration for the input array $A'''=(\bullet ^{2n-k+l}X\bullet ^{2n-l})_m$ as follows,

$$\begin{aligned} \begin{array}{rllllllll} q_0&{}\bullet &{}\bullet ^{2n-1-k+l}&{}X&{}\bullet ^{2n-l}&{}\#\\ (&{}\bullet &{}\bullet ^{2n-1-k+l}&{}X&{}\bullet ^{2n-l}&{}\#)_{m-1}\\ \end{array}\vdash _M^* \begin{array}{rllllllll} \bullet ^{i}&{}p&{}\bullet &{}\bullet ^{2n-1-i+j-k+l}&{}X&{}\bullet ^{2n-j-l}&{}\#\\ (\bullet ^{i}&{}&{}\bullet &{}\bullet ^{2n-1-i+j-k+l}&{}X&{}\bullet ^{2n-j-l}&{}\#)_{m-1}\\ \end{array}\vdash _M^* \ q_f' \end{aligned}$$

Since we have $l=k$ and $l>0$, the array $A'''\notin L'$, which is a contradiction. Hence this proves (i).   $\square$

Theorem 5

• (i) The family $\mathfrak {L}$(2-DLCRA) is incomparable with $\mathfrak {L}$(2-DRCRA)

• (ii) The family $\mathfrak {L}$(2-DLCRA) is incomparable with $\mathfrak {L}$(2-NRCRA)

• (iii) The family $\mathfrak {L}$(2-NLCRA) is incomparable with $\mathfrak {L}$(2-NRCRA)

• (iv) The family $\mathfrak {L}$(2-NLCRA) is incomparable with $\mathfrak {L}$(2-DRCRA)

• (v) The family $\mathfrak {L}$(2-NLCRA) is incomparable with $\mathfrak {L}$(2-DBCRA)

• (vi) The family $\mathfrak {L}$(2-NRCRA) is incomparable with $\mathfrak {L}$(2-DBCRA)

Proof

Follows from the proof of Theorem 4.   $\square$

5 Comparison with Siromoney Matrix Languages

In this section we give the comparison of the family of languages accepted by all the variants of 2-NCRFA with the family of Siromoney matrix languages. Here we consider RML$^T$ to be the transposition of RML.

Theorem 6

$\mathfrak {L}$(RML$^{T}$) $= \mathfrak {L}$(2-DCIRA) $=\mathfrak {L}$(2-NCIRA)

Proof

The transposition of any regular matrix language is accepted by a returning finite automaton (RFA), as can be seen in [3], which can be viewed as a 2-DCIRA where $\varDelta =\emptyset$ and which is also a particular 2-NCIRA. Hence it remains to prove that any 2-NCIRA accepts a regular matrix language.

While we consider a 2-NCIRA, during the application of $\varDelta$ rules, the automaton performs a circular-column-interchanging operation and it interchanges the column of the currently read symbol of the input array with the last column. So, once the last letter of the current reading row is known, a simulating automaton can remember the current last symbol of the row in its finite control to act correctly. Also we see that, initially the last symbol in the current row of the input can be guessed and finally, it can also be verified. Thus during the acceptance of any input array it can be easily seen that every row as well as column is regular. This simply corresponds with the definition of right-linear matrix grammars, where the vertical string of intermediate symbols are generated by using right-linear grammar rules followed by horizontal generation in parallel using right-linear grammar rules, yielding the regular matrix language. Hence any 2-NCIRA accepts a regular matrix language.   $\square$

Theorem 7

• 1. $\mathfrak {L}$(2-NLCRA) and $\mathfrak {L}$(CFML) are incomparable.

• 2. $\mathfrak {L}$(2-NRCRA) and $\mathfrak {L}$(CFML) are incomparable.

Proof

To Prove: $\mathfrak {L}$(2-NLCRA) − $\mathfrak {L}$(CFML) $\ne \emptyset$ and $\mathfrak {L}$(2-NRCRA) − $\mathfrak {L}$(CFML) $\ne \emptyset$. Consider the language,

$$\begin{aligned} L=\left\{ X= \begin{array}{c} X_1\\ \vdots \\ X_m \end{array}\in \{0,1,2\}^{**} \Bigg | \begin{array}{c} \hbox { each }X_i\hbox {'s are of size } 1\times n \text { and }\\ |X_i|_0=|X_i|_1=|X_i|_2, \forall \quad i=1,2,\ldots ,m \end{array}\right\} \end{aligned}$$

This language can be generated by any 2-NLCRA and 2-NRCRA, as can be seen in Example 1. But $L\notin$ $\mathfrak {L}$CFML. Hence, $\mathfrak {L}$(2-NLCRA) − $\mathfrak {L}$CFML $\ne \emptyset$ and $\mathfrak {L}$(2-NRCRA) − $\mathfrak {L}$(CFML) $\ne \emptyset$.

To prove: $\mathfrak {L}$(CFML) − $\mathfrak {L}$(2-NLCRA) $\ne \emptyset$ and $\mathfrak {L}$(CFML) − $\mathfrak {L}$(2-NRCRA) $\ne \emptyset$. Consider the language, $L'=\left\{ \begin{array}{ccccc} \;\;X^m&{}Y^m&{}X&{}Y^n&{}X^n\;\;\\ (X^m&{}\bullet ^m&{}X&{}\bullet ^n&{}X^n)_i\\ \;X^m&{}Y^m&{}X&{}Y^n&{}X^n\;\;\; \end{array}\; \bigg |\; n,m,i\ge 1 \right\}$. $L'\in$ $\mathfrak {L}$(CFML), as can be seen in [12], the vertical string of intermediate symbols can be generated by using right-linear grammar rules followed vertical generation in parallel using context-free grammar rules.

However, this language cannot be generated by any 2-NBCRA. We prove this by the method of contradiction. Let us assume that the language is accepted by some 2-NBCRA, $M=(Q,\varSigma , \delta , \varDelta ,q_0, F)$ with $|Q|=t$ and no (useless) loops. Let $A= \begin{array}{ccccc} \;\;X^{n+1}&{}Y^{n+1}&{}X&{}Y^n&{}X^n\;\;\\ (X^{n+1}&{}\bullet ^{n+1}&{}X&{}\bullet ^n&{}X^n)_i\\ \;X^{n+1}&{}Y^{n+1}&{}X&{}Y^n&{}X^n\;\;\; \end{array}$ with $n>2$, $i>0$ and $n>t$ be the input given to the automaton. By the pigeon hole principle, there exists a state, say p which appears at least twice during the computation on first row. Let the first occurrence of state p be reached in r steps which involves j normal transition, $l_1$ left column-revolving transition and $r_1$ right column-revolving transition,

Let the second occurrence of state p be reached in s steps which involves k normal transition, $l_2$ left column-revolving transition and $r_2$ right column-revolving transition,

Since the considered array A is in the language L, the computation reaches the accepting state, say $q_f\in Q$ i.e.,

We find that $l_2-r_2=0$. Otherwise, the computation

accepts the array $A'= \begin{array}{ccccc} \;\;X^{n+1-k+l_2-r_2}&{}Y^{n+1}&{}X&{}Y^n&{}X^{n-l_2+r_2}\;\;\\ (X^{n+1-k+l_2-r_2}&{}\bullet ^{n+1}&{}X&{}\bullet ^n&{}X^{n-l_2+r_2})_i\\ \;X^{n+1-k+l_2-r_2}&{}Y^{n+1}&{}X&{}Y^n&{}X^{n-l_2+r_2}\;\;\; \end{array}\notin L'.$ For same reason we also find that $l_2-r_2-k=0$ which implies $k=0$. But this is a contradiction to our assumption because it follows either that $r=s$ or M loops. This implies $L'$ is not accepted by any 2-NBCRA and hence by any 2-NLCRA and 2-NRCRA. Hence, $\mathfrak {L}$(CFML) − $\mathfrak {L}$(2-NLCRA) $\ne \emptyset$ and $\mathfrak {L}$(CFML) − $\mathfrak {L}$(2-NRCRA) $\ne \emptyset$.   $\square$

6 Closure Properties

In this section we discuss the closure properties of the family of languages accepted by any 2-DCIRA, 2-DLCRA, 2-DRCRA and 2-DBCRA.

Theorem 8

$\mathfrak {L}$(2-DCIRA) is closed under complementation and union.

Proof

From [14], RML is closed under complementation and union. By Theorem 6, this theorem is proved.   $\square$

Theorem 9

$\mathfrak {L}$(2-DLCRA), $\mathfrak {L}$(2-DRCRA) and $\mathfrak {L}$(2-DBCRA) are not closed under complementation.

Proof

Consider the language,

$$\begin{aligned} L=\left\{ X= \begin{array}{c} X_1\\ \vdots \\ X_m \end{array}\in \{0,1\}^{**} \Bigg | \begin{array}{c} \hbox { each }X_i\hbox {'s are of size } 1\times n \text { and }\\ |X_i|_0=|X_i|_1, \forall \quad i=1,2,\ldots ,m \end{array}\right\} \end{aligned}$$

By Theorem 2, the language $\bar{L}=\{\{0,1\}^{**} | \exists$ at least one row in which no. of 0s and 1s are not equal$\}$ is not accepted by any 2-DBCRA and hence by any 2-DLCRA and 2-DRCRA. But by Example 1, we see that the language L is accepted by some 2-DBCRA and hence by some 2-DLCRA and 2-DRCRA.   $\square$

Theorem 10

$\mathfrak {L}$(2-DLCRA), $\mathfrak {L}$(2-DRCRA) and $\mathfrak {L}$(2-DBCRA) are not closed under union.

Proof

Consider the languages,

$$\begin{aligned} L_1=\left\{ X= \begin{array}{c} X_1\\ \vdots \\ X_m \end{array}\in \{0,1\}^{**} \Bigg | \begin{array}{c} \hbox { each }X_i\hbox {'s are of size } 1\times n \text { and }\\ |X_i|_0=|X_i|_1, \forall \quad i=1,2,\ldots ,m \end{array}\right\} \end{aligned}$$

and $L_2=\{0\}^{**}$. The language $L_1$ can be accepted by a 2-DBCRA, as can be seen in Example 1. $L_2$ can be accepted by a 2-DBCRA, $M=(\{q_0\},\{0\},\{q_00\rightarrow q_0, q_0\#\rightarrow q_0\},\emptyset ,\emptyset ,q_0,\{q_0\})$. By the same reasoning as in the proof of Theorem 9 we can show that $L_1\cup L_2$ is not accepted by any 2-DBCRA and hence by any 2-DLCRA and 2-DRCRA.   $\square$

Theorem 11

$\mathfrak {L}$(2-DCIRA) is closed under column catenation, but not under row catenation.

Proof

From [14], RML is closed under column catenation, but not under row catenation. By Theorem 6, this theorem is proved.   $\square$

Theorem 12

$\mathfrak {L}$(2-DLCRA), $\mathfrak {L}$(2-DRCRA) and $\mathfrak {L}$(2-DBCRA) are neither closed under column catenation nor row catenation.

Proof

Consider the languages, $L_1=\left\{ \begin{array}{ccc} \;\;X^m&{}Y^m&{}X\;\;\\ (X^m&{}.^m&{}X)_i\\ \;X^m&{}Y^m&{}X\;\;\; \end{array}\; \bigg |\; m,i\ge 1 \right\}$ and $L_2=\left\{ \begin{array}{cc} \;\;Y^n&{}X^n\;\;\\ (.^n&{}X^n)_i\\ \;Y^n&{}X^n\;\;\; \end{array}\; \bigg |\; n,i\ge 1 \right\}$. Both the languages $L_1$ and $L_2$ belong to $\mathfrak {L}$(2-DLCRA). But the column catenation, does not belong to $\mathfrak {L}$(2-DBCRA), as seen in proof of Theorem 7. This proves that $\mathfrak {L}$(2-DLCRA) and $\mathfrak {L}$(2-DBCRA) are not closed under column catenation.

If we consider the language,

$$\begin{aligned} L_3=\left\{ X= \begin{array}{c} X_1\\ \vdots \\ X_m \end{array}\in \{0,1\}^{**} \Bigg | \begin{array}{c} \hbox { each }X_i\hbox {'s are of size } 1\times n \text { and }\\ |X_i|_0=|X_i|_1, \forall \quad i=1,2,\ldots ,m \end{array}\right\} \end{aligned}$$

belonging to $\mathfrak {L}$(2-DLCRA) and also $\mathfrak {L}$(2-DRCRA), it is clear that $L_3\ominus L_2$ does not even belong to $\mathfrak {L}$(2-DBCRA), because the columns shuffling involved during the simulation of the automaton accepting $L_2$ makes the simulation of the automaton accepting $L_3$ impossible. This proves that $\mathfrak {L}$(2-DLCRA), $\mathfrak {L}$(2-DRCRA) and $\mathfrak {L}$(2-DBCRA) is not closed under row catenation.

Now we consider the language,

$$\begin{aligned} L_4=\left\{ X= \begin{array}{c} 2X_1\\ \vdots \\ 2X_m \end{array}\in \{0,1,2\}^{**} \Bigg | \begin{array}{c} \hbox { each }X_i\text {'s are of size } 1\times n \text { and }\\ |X_i|_0=|X_i|_1, \forall \quad i=1,2,\ldots ,m \end{array}\right\} \end{aligned}$$

Clearly, the languages $L_3$ and $L_4$ belong to 2-DRCRA, but the language does not belong to 2-DRCRA (can be proved by a similar argument as in Theorem 1). Hence $\mathfrak {L}$(2-DRCRA) are not closed under column catenation.

Theorem 13

$\mathfrak {L}$(2-DCIRA) is closed under column Kleene star, but not under row Kleene star.

Proof

The proof follows from Theorem 11.   $\square$

Theorem 14

$\mathfrak {L}$(2-DLCRA), $\mathfrak {L}$(2-DRCRA) and $\mathfrak {L}$(2-DBCRA) are neither closed under column Kleene star nor row Kleene star.

Proof

The proof follows from Theorem 12.   $\square$

Theorem 15

$\mathfrak {L}$(2-DCRFA) is not closed under quarter turn and transpose.

Proof

For $\mathfrak {L}$(2-DCIRA) the properties are true, from [14] and Theorem 6.

Consider the language,

$L(M)=\left\{ X= {\begin{matrix} X_1\\ \vdots \\ X_m \end{matrix}}\in \{0,1\}^{**} \Bigg | \begin{array}{c} X_i= a_{i1} a_{i2}\ldots a_{in} \\ |X_i|_0=|X_i|_1, \forall \quad i=1,2,\ldots ,m \end{array}\right\}$. This language can be generated by some 2-DBCRA, and hence by some 2-DLCRA and 2-DRCRA as can be seen in Example 1. Let us represent the quarter turn of this language by $L^{QT}$ and we have,

$$\begin{aligned} L^{QT}=\left\{ X= X_m \ldots X_1\in \{0,1\}^{**} |\; X_i= {\begin{matrix} a_{i1}\\ \vdots \\ a_{in} \end{matrix}} , |X_i|_0=|X_i|_1, \forall \ i=1,2,\ldots ,m\right\} . \end{aligned}$$

This language cannot be generated by any 2-DCRFA, because no such automaton can accept the input X from $L^{QT}$ with the condition $|X_i|_0=|X_i|_1,\forall \ i=1,2,\ldots ,k$. This proves that $\mathfrak {L}$(2-DBCRA) is not closed under quarter turn.

Let us represent the transpose of the language L by $L^T$ and we have, $L^{T}=\left\{ X= X_1 \ldots X_m\ \in \{0,1\}^{**} |\, X_i= {\begin{matrix} a_{i1}\\ \vdots \\ a_{in}\end{matrix}}, |X_i|_0=|X_i|_1, \forall \ i=1,2,\ldots ,m\right\}$. By the same argument as discussed for $L^{QT}$, we see that there is no 2-DCRFA to accept $L^T$. This proves that $\mathfrak {L}$(2-DBCRA) is not closed under transpose.   $\square$

Theorem 16

$\mathfrak {L}$(2-DCRFA) is closed under half turn, reflection on rightmost vertical and reflection on base.

Proof

For $\mathfrak {L}$(2-DCIRA) the property is true, from [14] and Theorem 6. We shall give the proof for $\mathfrak {L}$(2-DRCRA) and reflection about the rightmost vertical, proof being similar for the rest of the cases. Let $M=(Q,\varSigma , \delta , \varDelta ,q_0, F)$ be a 2-DRCRA that accepts the language $L=L(M)$. We now construct a 2-DRCRA, $M'$ that accepts the language obtained by taking reflection on the rightmost vertical of L represented by $L^{RB}$. $M'=(Q\cup \{q_0'\},\varSigma , \delta ', \varDelta , q_0', F')$, where $\delta '=\delta \cup \{q_0'\rightarrow q \ |\ p\#\rightarrow q\in \delta \}\cup \{p\rightarrow q_0 \ |\ p\in Q\}\cup \{q\rightarrow p\ |\ q\in F, p\in Q\}$ and $F'=\{q\ |\ q_0\rightarrow q_1, q_1\rightarrow q_2, \ldots , q_{n-1}\rightarrow q_n, q_n\#\rightarrow q \in \delta '\}$. Clearly, $L(M')= L^{RB}$.   $\square$

7 Application

One of the applications of this newly constructed automata is in the field of steganography [6]. Steganography is the art and science of hiding information by embedding messages within others. This hidden information can be plain text, cipher text, or even images. Steganographic communications hide often in plain sight, whereas encrypted communications in Cryptography are very obvious of the fact that they are sending secrets.

Here we consider hiding text messages behind some pictures which can be retrieved only by giving them as input in the newly constructed automata and arriving at the final configuration. For example, let us consider the 2-DRCRA automaton from Example 1 and an array $\begin{array}{cccccc} 2&{}2&{}1&{}0&{}1&{}0\\ 2&{}1&{}0&{}1&{}0&{}2\\ 0&{}1&{}2&{}1&{}0&{}2\\ \end{array}$. Let $\begin{array}{cccccc} T&{}\square &{}\square &{}S&{}H&{}I\\ I&{}\square &{}\square &{}A&{}S&{}\square \\ E&{}S&{}T&{}E&{}C&{}R\\ \end{array}$ be the scrambled hidden message behind the array A. Now to get the proper hidden message $\begin{array}{cccccc} \square &{}T&{}H&{}I&{}S&{}\square \\ \square &{}I&{}S&{}\square &{}A&{}\square \\ S&{}E&{}C&{}R&{}E&{}T\\ \end{array}$, the array A is given as the input to the automaton and an accepting configuration has to be reached. The working of this automaton on array A along with the hidden message is as follows:

8 Conclusion

It is worth examining the decidability results (non-emptiness, membership, finiteness, etc.) of these automata and explore their further applications in character recognition and floor designs. Construction of two-dimensional automaton which involves both column-revolving and row-revolving can also be studied.