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

При любом положительном целом 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 _m a`

где 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. — С. -239. — 294 с.