Операции
Некоторые операции могут быть использованы для того, чтобы порождать новые языки из данных. Предположим, что
и
являются языками, определёнными над некоторым общим алфавитом.
- Конкатенация (сцепление)
содержит все слова, удовлетворяющие форме
, где
— это слово из
, а
— слово из
.
- Пересечение
содержит все слова, содержащиеся и в
, и в
.
- Объединение
содержит все слова, содержащиеся в
или в
.
- Дополнение языка
содержит все слова алфавита, которые не содержатся в
.
- Правое отношение
содержит все слова
, для которых существует слово
в
такое, что
находилось в
.
- Замыкание Клини
содержит все слова, которые могут быть записаны в форме
, где
содержится в
и
. Следует помнить, что это включает и пустое слово
, так как
допустимо по условию.
- Обращение
содержит обращённые слова из
.
- Смешение
и
содержит все слова, которые могут быть записаны в форме
, где
и
являются такими словами, что связь
находится в
, а
являются такими словами, что
находятся в
.
Литература
- Гладкий А. В. Формальные грамматики и языки. — М.: Наука, 1973. — 368 с.
- Хопкрофт, Дж., Мотвани, Р., Дж. Ульман. Введение в теорию автоматов, языков и вычислений. — М.: Вильямс, 2002 (пер. издания Addison Wesley). — 528 с. — ISBN 5-8459-0261-4
- Кревский И. Г., Селивёрстов М. Н., Григорьева К. В. Формальные языки, грамматики и основы построения трансляторов: Учебное пособие / Под ред. А. М. Бершадского. — Пенза: Изд-во Пенз. гос. ун-та, 2002. — 124 с.
- Мартыненко Б. К. Языки и трансляции: Учебное пособие. — СПб.: Издательство С.-Петербургского университета, 2003. — 235 с.
- Серебряков В. А., Галочкин М. П., Гончар Д. Р., Фуругян М. Г. Теория и реализация языков программирования — М.: МЗ-Пресс, 2006 г., 2-е изд. — ISBN 5-94073-094-9
- Пентус А. Е., Пентус М. Р. Математическая теория формальных языков. — М.: Интернет-университет информационных технологий, Бином. Лаборатория знаний, 2006. — 248 с.
- Фомичёв В. С. Формальные языки, грамматики и автоматы: Курс лекций — Интернет-публикация, 2006.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .