WikiDer > Уравнение языка

Language equation

Уравнения языка математические утверждения, которые напоминают числовые уравнения, но переменные принимают значения формальные языки а не числа. Вместо арифметических операций в числовых уравнениях переменные объединяются с помощью языковых операций. Среди наиболее распространенных операций на двух языках А и B являются установить союз АB, то установить пересечение АB, а конкатенация АB. Наконец, как операция, требующая одного операнд, набор А* обозначает Клини звезда языка А. Следовательно, языковые уравнения могут использоваться для представления формальные грамматики, поскольку языки, порожденные грамматикой, должны быть решением системы языковых уравнений.

Языковые уравнения и контекстно-свободные грамматики

Гинзбург и Рис[1]дал альтернативное определение контекстно-свободные грамматики языковыми уравнениями. К каждой контекстно-свободной грамматике , связана система уравнений от переменных . Каждая переменная неизвестный язык и определяется уравнением куда , ..., все постановки для . Гинзбург и Райс использовали итерация с фиксированной точкой аргумент, чтобы показать, что решение всегда существует, и доказал, что назначение это наименьшее решение к этой системе,[уточнить] т.е. любое другое решение должно быть подмножество[уточнить] этого.

Например, грамматика соответствует системе уравненийкоторый имеет в качестве решения все надмножества .

Аналогично языковые уравнения с добавленным пересечением соответствуют конъюнктивные грамматики.[нужна цитата]

Языковые уравнения и конечные автоматы

Бжозовский и Лейсс[2] учился уравнения левого языка где каждая конкатенация выполняется с одноэлементным постоянным языком слева, например с переменной , но нет ни . Каждое уравнение имеет вид с одной переменной в правой части. Каждый недетерминированный конечный автомат имеет такое соответствующее уравнение с использованием левой конкатенации и объединения, см. рис. 1. Если разрешена операция пересечения, уравнения соответствуют переменные конечные автоматы.

Рис.1: А конечный автомат с соответствующей системой уравнений , куда это пустое слово.[2]:21

Баадер и Нарендран[3] изучал уравнения используя левую конкатенацию и объединение и доказал, что их проблема выполнимости EXPTIME-завершено.

Проблема Конвея

Конвей[4] предложил следующую задачу: заданный постоянный конечный язык , является наибольшим решением уравнения всегда регулярно? Эта проблема была изучена Кархумяки и Петре[5][6] который дал утвердительный ответ в частном случае. Категорически отрицательный ответ на проблему Конвея дал Kunc[7] кто построил конечный язык такое, что наибольшее решение этого уравнения не является рекурсивно перечислимым.

Kunc[8] также доказал, что наибольшее решение неравенства всегда регулярно.

Уравнения языка с булевыми операциями

Языковые уравнения с конкатенацией и булевыми операциями впервые были изучены Парих, Чандра, Halpern и Мейер[9] который доказал, что проблема выполнимости для данного уравнения неразрешима, и что если система языковых уравнений имеет единственное решение, то это решение рекурсивно. Потом, Охотин[10] доказал, что проблема невыполнимости Повторно завершить и что каждый рекурсивный язык является единственным решением некоторого уравнения.

Языковые уравнения над унарным алфавитом

Для однобуквенного алфавита Лейсс[11] открыл уравнение первого языка с нерегулярным решением, используя операции дополнения и конкатенации. Позже Джео[12] показал, что нерегулярные унарные языки могут быть определены языковыми уравнениями с объединением, пересечением и конкатенацией, эквивалентными конъюнктивные грамматики. Этим методом Джео и Охотин[13] доказал, что каждый рекурсивный унарный язык является единственным решением некоторого уравнения.

Смотрите также

Рекомендации

  1. ^ Гинзбург, Сеймур; Райс, Х. Гордон (1962). «Две семьи языков, связанные с АЛГОЛом». Журнал ACM. 9 (3): 350–371. Дои:10.1145/321127.321132. ISSN 0004-5411.
  2. ^ а б Brzozowski, J.A .; Лейсс, Э. (1980). «Об уравнениях для регулярных языков, конечных автоматов и последовательных сетей». Теоретическая информатика. 10 (1): 19–35. Дои:10.1016/0304-3975(80)90069-9. ISSN 0304-3975.
  3. ^ Баадер, Франц; Нарендран, Палиат (2001). «Объединение понятийных терминов в логике описания». Журнал символических вычислений. 31 (3): 277–305. Дои:10.1006 / jsco.2000.0426. ISSN 0747-7171.
  4. ^ Конвей, Джон Хортон (1971). Регулярная алгебра и конечные машины. Чепмен и Холл. ISBN 978-0-486-48583-6.
  5. ^ Кархумяки, Юхани; Петре, Ион (2002). "Проблема Конвея для трехсловных наборов". Теоретическая информатика. 289 (1): 705–725. Дои:10.1016 / S0304-3975 (01) 00389-9. ISSN 0304-3975.
  6. ^ Кархумяки, Юхани; Петре, Ион (2002). Подход точки ветвления к проблеме Конвея. Конспект лекций по информатике. 2300. С. 69–76. Дои:10.1007/3-540-45711-9_5. ISBN 978-3-540-43190-9. ISSN 0302-9743.
  7. ^ Кунч, Михал (2007). «Сила коммутации с конечными наборами слов». Теория вычислительных систем. 40 (4): 521–551. Дои:10.1007 / s00224-006-1321-z. ISSN 1432-4350.
  8. ^ Кунч, Михал (2005). «Регулярные решения языковых неравенств и квазипорядков». Теоретическая информатика. 348 (2–3): 277–293. Дои:10.1016 / j.tcs.2005.09.018. ISSN 0304-3975.
  9. ^ Парих, Рохит; Чандра, Ашок; Халперн, Джо; Мейер, Альберт (1985). «Уравнения между обычными терминами и приложение для обработки логики». SIAM Журнал по вычислениям. 14 (4): 935–942. Дои:10.1137/0214066. ISSN 0097-5397.
  10. ^ Охотин, Александр (2010). «Решение задач для языковых уравнений». Журнал компьютерных и системных наук. 76 (3–4): 251–266. Дои:10.1016 / j.jcss.2009.08.002. ISSN 0022-0000.
  11. ^ Лейсс, Э. (1994). «Неограниченное дополнение в языковых уравнениях над однобуквенным алфавитом». Теоретическая информатика. 132 (1–2): 71–84. Дои:10.1016/0304-3975(94)90227-5. ISSN 0304-3975.
  12. ^ Jeż, Артур (2008). «Конъюнктивные грамматики порождают нерегулярные унарные языки». Международный журнал основ информатики. 19 (3): 597–615. Дои:10.1142 / S012905410800584X. ISSN 0129-0541.
  13. ^ Jeż, Артур; Охотин, Александр (2014). «Вычислительная полнота уравнений над наборами натуральных чисел». Информация и вычисления. 237: 56–94. CiteSeerX 10.1.1.395.2250. Дои:10.1016 / j.ic.2014.05.001. ISSN 0890-5401.

внешняя ссылка