formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of sy ...

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 models. Some

formal system A formal system is an abstract structure used for inferring theorems from axioms according to a set of rules. These rules, which are used for carrying out the inference of theorems from axioms, are the logical calculus of the formal system. A form ...

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