Язык Дика

Языком Дика (англ. Dyck language) над 2n буквами называется контекстно-свободный язык над алфавитом

{a₁,b₁,a₂,b₂,…a_n,b_n}, порождаемый грамматикой S → е, S → a₁ S b₁ S, . . . , S → a_nSb_nS.

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

Ограниченный язык Дика

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

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

S→SS

S→aSa`,bSb`,…

S→aa`,bb`,…

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

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

Простые цепочки по Дику

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

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

g=xf₁…f_m<math>\overline {x}</math>,

где f_i<math>\in</math>D_xi, x_i<math>\ne</math><math>\overline {x}</math>, i=1,…,m.

Пример

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

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

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

Построение однозначной КС-грамматики, порождающей язык Дика

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

{a, a`,b, b`}

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

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

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

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

af₁…f_ma`

где f_i<math>\in</math>D_xi, x_i<math>\ne</math><math>\overline {a}</math>

(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)Задают некоторую однозначную грамматику.

Примечание:

Эта грамматика однозначна, так как она порождает слева направо Д-простые сомножители цепочки <math>\in</math> 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 с.

Отрывок, характеризующий Язык Дика

Михаил Иваныч встал и пошел в кабинет. Но только что он вышел, старый князь, беспокойно оглядывавшийся, бросил салфетку и пошел сам.
– Ничего то не умеют, все перепутают.
Пока он ходил, княжна Марья, Десаль, m lle Bourienne и даже Николушка молча переглядывались. Старый князь вернулся поспешным шагом, сопутствуемый Михаилом Иванычем, с письмом и планом, которые он, не давая никому читать во время обеда, положил подле себя.
Перейдя в гостиную, он передал письмо княжне Марье и, разложив пред собой план новой постройки, на который он устремил глаза, приказал ей читать вслух. Прочтя письмо, княжна Марья вопросительно взглянула на отца.
Он смотрел на план, очевидно, погруженный в свои мысли.
– Что вы об этом думаете, князь? – позволил себе Десаль обратиться с вопросом.
– Я! я!.. – как бы неприятно пробуждаясь, сказал князь, не спуская глаз с плана постройки.
– Весьма может быть, что театр войны так приблизится к нам…
– Ха ха ха! Театр войны! – сказал князь. – Я говорил и говорю, что театр войны есть Польша, и дальше Немана никогда не проникнет неприятель.
Десаль с удивлением посмотрел на князя, говорившего о Немане, когда неприятель был уже у Днепра; но княжна Марья, забывшая географическое положение Немана, думала, что то, что ее отец говорит, правда.
– При ростепели снегов потонут в болотах Польши. Они только могут не видеть, – проговорил князь, видимо, думая о кампании 1807 го года, бывшей, как казалось, так недавно. – Бенигсен должен был раньше вступить в Пруссию, дело приняло бы другой оборот…
– Но, князь, – робко сказал Десаль, – в письме говорится о Витебске…
– А, в письме, да… – недовольно проговорил князь, – да… да… – Лицо его приняло вдруг мрачное выражение. Он помолчал. – Да, он пишет, французы разбиты, при какой это реке?
Десаль опустил глаза.
– Князь ничего про это не пишет, – тихо сказал он.
– А разве не пишет? Ну, я сам не выдумал же. – Все долго молчали.
– Да… да… Ну, Михайла Иваныч, – вдруг сказал он, приподняв голову и указывая на план постройки, – расскажи, как ты это хочешь переделать…
Михаил Иваныч подошел к плану, и князь, поговорив с ним о плане новой постройки, сердито взглянув на княжну Марью и Десаля, ушел к себе.
Княжна Марья видела смущенный и удивленный взгляд Десаля, устремленный на ее отца, заметила его молчание и была поражена тем, что отец забыл письмо сына на столе в гостиной; но она боялась не только говорить и расспрашивать Десаля о причине его смущения и молчания, но боялась и думать об этом.
Ввечеру Михаил Иваныч, присланный от князя, пришел к княжне Марье за письмом князя Андрея, которое забыто было в гостиной. Княжна Марья подала письмо. Хотя ей это и неприятно было, она позволила себе спросить у Михаила Иваныча, что делает ее отец.
– Всё хлопочут, – с почтительно насмешливой улыбкой, которая заставила побледнеть княжну Марью, сказал Михаил Иваныч. – Очень беспокоятся насчет нового корпуса. Читали немножко, а теперь, – понизив голос, сказал Михаил Иваныч, – у бюра, должно, завещанием занялись. (В последнее время одно из любимых занятий князя было занятие над бумагами, которые должны были остаться после его смерти и которые он называл завещанием.)