Язык Дика

Языком Дика (англ. 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.

Пример порождения языка Дика может быть представлен следующей грамматикой:

S→SS

S→aSa`,bSb`,…

S→aa`,bb`,…

Вывод для цепочки abbaa`b`cc`bb`b`a`

так же возможны и другие выводы данной цепочки

(Д-простые цепочки)

Цепочка 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.

Пример

Д-простая цепочка: a`baa`bb`b`a

Рассмотрим данную цепочку с первого элемента цепочки — a`. Парой для него будет последний элемент цепочки — a. Критерием для пары является отсутствие идентичности элементов между собой. Эти элементы являются спаренными и обозначается: a${\displaystyle \neq }$${\displaystyle {\overline {a}}}$`

D_x это множество всех Д-простых цепочек, которые начинаются элементом x и оканчиваются элементом ${\displaystyle {\overline {x}}}$.

Заданный алфавит

{a, a`,b, b`}

Нетерминальные символы

{D_a, D_{a`</sub>, D<sub>b</sub>, D<sub>b`}, A} ${\displaystyle \in }$ некоторому языку, который состоит из конкатенаций любых цепочек ${\displaystyle \in }$ D_a${\displaystyle \cup }$D_{a`</sub>${\displaystyle \cup }$D<sub>b</sub>${\displaystyle \cup }$ D<sub>b`}

E — пустая цепочка.

D_a содержит, помимо цепочки aa`, все цепочки, имеющие вид

af₁…f_ma`

где f_i${\displaystyle \in }$D_xi, x_i${\displaystyle \neq }$${\displaystyle {\overline {a}}}$

(1) D_a,=aAa`=aa`

(2) A=(D_{a`</sub>+D<sub>b</sub>+ D<sub>b`})(A+E)

Языку Дика D соответствует уравнение:

(3) D*=(D_a+D_{a`</sub>+D<sub>b</sub>+ D<sub>b`})

Уравнения типов (1) и (2) вместе с уравнением (3) задают некоторую однозначную грамматику.

Примечание:

Эта грамматика однозначна, так как она порождает слева направо Д-простые сомножители цепочки ${\displaystyle \in }$ D*.

Для построения данной грамматики мы исключаем множества D_{a`</sub>, D<sub>b`} и т. д.

Цепочки начинающиеся штрихованными элементами, не рассматриваются.

D_a=aUa`+aa`

D_b=bUb`+bb`

U=(D_a+D_b)(U+E)

D*_r=(D_a+D_b)D*_r+E

• Пентус А. Е., Пентус М. Р. Теория формальных языков: Учебное пособие. — М.: Изд-во ЦПИ при механико-математическом ф-те МГУ, 2004. — 80 с.
• Гросс М., Лантен А. Теория формальных грамматик. — М.: Мир, 1971. — С. 232-239. — 294 с.

Для улучшения этой статьи желательно: Оформить статью по правилам. Оформить список литературы. Проставить сноски, внести более точные указания на источники. Оформить математические формулы Пожалуйста, после исправления проблемы исключите её из списка параметров. После устранения всех недостатков этот шаблон может быть удалён любым участником.