Уравнение языка - Language equation

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

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

Гинзбург и Рис^[1]дал альтернативное определение контекстно-свободные грамматики языковыми уравнениями. К каждой контекстно-свободной грамматике ${displaystyle G=(V,Sigma ,R,S)}$, связана система уравнений от переменных ${displaystyle V}$. Каждая переменная ${displaystyle Xin V}$ неизвестный язык ${displaystyle Sigma }$ и определяется уравнением ${displaystyle X=alpha _{1}cup ldots cup alpha _{m}}$ куда ${displaystyle X o alpha _{1}}$, ..., ${displaystyle X o alpha _{m}}$ все постановки для ${displaystyle X}$. Гинзбург и Райс использовали итерация с фиксированной точкой аргумент, чтобы показать, что решение всегда существует, и доказал, что назначение ${displaystyle X=L_{G}(X)}$ это наименьшее решение к этой системе,^{[уточнить ]} т.е. любое другое решение должно быть подмножество^{[уточнить ]} этого.

Например, грамматика ${displaystyle S o aScmid bmid S}$соответствует системе уравнений${displaystyle S=({a}cdot Scdot {c})cup {b}cup S}$который имеет в качестве решения все надмножества ${displaystyle {a^{n}bc^{n}mid nin {mathcal {N}}}}$.

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

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

Бжозовский и Лейсс^[2] учился уравнения левого языка где каждая конкатенация выполняется с одноэлементным постоянным языком слева, например ${displaystyle {a}cdot X}$ с переменной ${displaystyle X}$, но нет ${displaystyle Xcdot Y}$ ни ${displaystyle Xcdot {a}}$. Каждое уравнение имеет вид ${displaystyle X_{i}=F(X_{1},...,X_{k})}$ с одной переменной в правой части. Каждый недетерминированный конечный автомат имеет такое соответствующее уравнение с использованием левой конкатенации и объединения, см. рис. 1. Если разрешена операция пересечения, уравнения соответствуют переменные конечные автоматы.

Рис.1: А конечный автомат с соответствующей системой уравнений ${displaystyle S_{1}=1cdot S_{1}cup 0cdot S_{2}cup {epsilon }}$, ${displaystyle S_{2}=1cdot S_{2}cup 0cdot S_{1}}$ куда ${displaystyle epsilon }$ это пустое слово.^[2]:21

Баадер и Нарендран^[3] изучал уравнения ${displaystyle F(X_{1},ldots ,X_{k})=G(X_{1},ldots ,X_{k})}$ используя левую конкатенацию и объединение и доказал, что их проблема выполнимости EXPTIME-завершено.

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

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

Kunc^[8] также доказал, что наибольшее решение неравенства ${displaystyle LXsubseteq XL}$ всегда регулярно.

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

Языковые уравнения с конкатенацией и булевыми операциями впервые были изучены Парих, Чандра, 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.

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

• Практикум по теории и приложениям языковых уравнений (TALE 2007)