Язык Дика

Язык Дика

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

{a1,b1,a2,b2,…an,bn}, порождаемый грамматикой S → е, S → a1 S b1 S, . . . , S → anSbnS.

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

Содержание

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

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

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

S→SS

S→aSa`,bSb`,…

S→aa`,bb`,…

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

Таблица1.png

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

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

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

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

g=xf1…fm\overline {x},

где fi\inDxi, xi\ne\overline {x}, i=1,…,m.

Пример

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

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

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

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

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

{a, a`,b, b`}

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

{Da, Da`, Db, Db`, A} \in Некоторму языку, который состоит из конкатенаций любых цепочек \in Da\cup Da`\cup Db\cup Db`

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

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

af1…fma`

где fi\inDxi, xi\ne\overline {a}

(1) Da,=aAa`=aa`

(2) A=(Da`+Db+ Db`)(A+E)

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

(3) D*=(Da+Da`+Db+ Db`)

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

Примечание:

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

Однозначная грамматика, порождающая ограниченный язык Дика

Для посторения данной грамматики мы исключаем множества Da`, Db` и т. д.

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

Da=aUa`+aa`

Db=bUb`+bb`

U=(Da+Db)(U+E)

D*r=(Da+Db)D*r+E

Литература

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

Wikimedia Foundation. 2010.

Поможем решить контрольную работу

Полезное


Смотреть что такое "Язык Дика" в других словарях:

  • Контекстно-свободный язык — Контекстно свободная грамматика (КС грамматика, бесконтекстная грамматика) частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются нетерминалами. Смысл термина «контекстно свободная»… …   Википедия

  • Забавные приключения Дика и Джейн (фильм) — Забавные приключения Дика и Джейн Fun with Dick and Jane Жанр романтическая комедия Режиссёр Тед Котчефф Продюсер Питер Ба …   Википедия

  • Забавные приключения Дика и Джейн — Fun with Dick and Jane Жанр романтическая комедия Режиссёр Тед Котчефф Продюсер Питер Барт Макс Палевский …   Википедия

  • Бесконтекстная грамматика — Контекстно свободная грамматика (КС грамматика, бесконтекстная грамматика) частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются нетерминалами. Смысл термина «контекстно свободная»… …   Википедия

  • КС-грамматика — Контекстно свободная грамматика (КС грамматика, бесконтекстная грамматика) частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются нетерминалами. Смысл термина «контекстно свободная»… …   Википедия

  • Контекстно-свободные — Контекстно свободная грамматика (КС грамматика, бесконтекстная грамматика) частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются нетерминалами. Смысл термина «контекстно свободная»… …   Википедия

  • Контекстно-свободная грамматика — (КС грамматика, бесконтекстная грамматика)  частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами. Смысл термина «контекстно свободная» заключается в том,… …   Википедия

  • Правильная скобочная последовательность — (ПСП)  частный случай скобочной последовательности. Правильные скобочные последовательности образуют язык Дика и формально определяются следующим образом: (пустая строка)  ПСП ПСП, взятая в скобки одного типа  ПСП ПСП, к которой… …   Википедия

  • SCAPULA ALATA — SCAPULA ALATA, крыловидная лопатка, признак, указывающий на слабость мышц, фиксирующих лопатку относительно грудной клетки; он состоит в том, что лопатка принимает крыловидное положение, медиальный край и особенно нижний угол ее отстает от… …   Большая медицинская энциклопедия

  • Большое лунное надувательство — Лунные мышелюди, животные и пейзаж. Литография XIX века …   Википедия

Книги

Другие книги по запросу «Язык Дика» >>


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»