formal language In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet". The alphabet of a formal language consists of symbols that concatenate into strings (also c ...

theory, a picture language is a set of ''pictures'', where a picture is a 2D array of characters over some alphabet. For example, the language

L = \left \

defines the language of rectangles composed of the character

a

. This language

L

contains pictures such as:

\begina\\a\end,
\begin a&a\\a&a\\a&a\end,
\begin a&a&a\\a&a&a\\a&a&a\\a&a&a\end
\in L

The study of picture languages was initially motivated by the problems of pattern recognition and image processing, but two-dimensional patterns also appear in the study of

cellular automata A cellular automaton (pl. cellular automata, abbrev. CA) is a discrete model of computation studied in automata theory. Cellular automata are also called cellular spaces, tessellation automata, homogeneous structures, cellular structures, tessel ...

and other

parallel computing Parallel computing is a type of computing, computation in which many calculations or Process (computing), processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. ...

models. Some

formal system A formal system is an abstract structure and formalization of an axiomatic system used for deducing, using rules of inference, theorems from axioms. In 1921, David Hilbert proposed to use formal systems as the foundation of knowledge in ma ...

s have been created to define picture languages, such as array grammars and tiling systems.

References

* D. Giammaresi, A. Restivo.
Two-dimensional languages
In A. Salomaa, G. Rozenberg (Eds.), ''Handbook of Formal Languages'', Vol. 3, Beyond Words, Springer, Berlin, 1997, pp. 215–267. Formal languages {{formalmethods-stub