Язык Дика

Материал из Википедии — свободной энциклопедии

Для улучшения статьи желательно: Найти и установить ссылки из других статей Википедии

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

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

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

Содержание 1 Ограниченный язык Дика 2 Простые цепочки по Дику 3 Построение однозначной КС-грамматики, порождающей язык Дика 4 Однозначная грамматика, порождающая ограниченный язык Дика 5 Литература

[править] Ограниченный язык Дика

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

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

S—>SS

S—>aSa`,bSb`,…

S—>aa`,bb`,…

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

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

[править] Простые цепочки по Дику

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

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

g=xf₁…f_m,

где f_iD_xi, x_i, i=1,…,m.

Пример

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

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

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

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

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

{a, a`,b, b`}

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

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

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

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

af₁…f_ma`

где f_iD_xi, x_i

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

Примечание:

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