Язык Дика

Определение:

Пусть [math]A = \{a_1, a_2, \ldots , a_k\}[/math] — произвольный конечный набор различных букв. Словом в алфавите [math]A[/math] называется произвольная конечная последовательность буквa [math]a_1 a_2 \ldots a_m,[/math] где [math]a_i \in A , i = 1, \ldots , m[/math]. Число [math]m[/math] называется длиной слова. Языком над алфавитом [math]A[/math] называется произвольное (конечное или бесконечное) множество слов в алфавите [math]A[/math].

Пустое слово [math]\lambda[/math] имеет длину [math]0[/math] и может входить или не входить в язык.

Определение:

Язык Дика (англ. Dyck language) — множество правильных скобочных структур вместе с пустой структурой, образующее язык над алфавитом [math]\{a, b\}[/math].