Язык Дика

---

Языком Дика (англ. Dyck language) над 2n буквами называется контекстно-свободный язык, который состоит из сбалансированных наборов скобок n разных видов. Формально это язык над алфавитом{a₁,b₁,a₂,b₂,…a_n,b_n}, порождаемый грамматикой S → ε, S → a₁Sb₁S, . . . , S → a_nSb_nS.

При любом положительном целом n грамматика является однозначной. Словами этого языка являются последовательности правильно вложенных скобок n типов.

Ограниченный язык Дика над алфавитом B=U${\displaystyle \cup }$U` есть множество тех слов (цепочек) в алфавите B, которые переводятся в ε последовательным вычеркиванием пар аа`,bb`,… Но не пар a`a, b`b.

Цепочка d${\displaystyle \in }$D* называется Простой цепочкой по Дику если никакое непустое начало цепочки d отличное от самой d, не принадлежит D*. Заменяя слово «начало» на слово «конец», получаем эквивалентное определение.

g=xf₁…f_m${\displaystyle {\overline {x}}}$,

где f_i${\displaystyle \in }$D_xi, x_i${\displaystyle \neq }$${\displaystyle {\overline {x}}}$, i=1,…,m.

---