Языковое уравнение

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

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

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

Например, грамматика $S\to aSc\mid b\mid S$ соответствует системе уравнений $S=(\{a\}\cdot S\cdot \{c\})\cup \{b\}\cup S$ которое имеет решением каждое надмножество $\{a^{n}bc^{n}\mid n\in {\mathcal {N}}\}$ .

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

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

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

Рис. 1: Конечный автомат с связанной с ним системой уравнений $S_{1}=1\cdot S_{1}\cup 0\cdot S_{2}\cup \{\epsilon \}$ , $S_{2}=1\cdot S_{2}\cup 0\cdot S_{1}$ где $\epsilon$ это пустое слово. ^[2]^: 21

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

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

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

Кунц ^[8] также доказал, что наибольшее решение неравенства $LX\subseteq XL$ всегда регулярен.

Языковые уравнения с логическими операциями

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

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

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

См. также

Ссылки

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

Внешние ссылки

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

[GinsburgRice1962-1] Гинзбург, Сеймур; Райс, Х. Гордон (1962). «Два семейства языков, связанных с АЛГОЛом» . Журнал АКМ . 9 (3): 350–371. дои : 10.1145/321127.321132 . ISSN 0004-5411 . S2CID 16718187 .

[BrzozowskiLeiss1980-2] Jump up to: ^а ^б Бжозовский, Дж. А.; Лейсс, Э. (1980). «Об уравнениях регулярных языков, конечных автоматов и последовательных сетей» . Теоретическая информатика . 10 (1): 19–35. дои : 10.1016/0304-3975(80)90069-9 . ISSN 0304-3975 .

[BaaderNarendran2001-3] Баадер, Франц; Нарендран, Палиат (2001). «Унификация понятийных терминов в логике описания» . Журнал символических вычислений . 31 (3): 277–305. дои : 10.1006/jsco.2000.0426 . ISSN 0747-7171 .

[4] Конвей, Джон Хортон (1971). Регулярная алгебра и конечные машины . Чепмен и Холл. ISBN 978-0-486-48583-6 .

[KarhumäkiPetre2002a-5] Кархумяки, Юхани; Петре, Ион (2002). «Задача Конвея для наборов из трех слов» . Теоретическая информатика . 289 (1): 705–725. дои : 10.1016/S0304-3975(01)00389-9 . ISSN 0304-3975 .

[KarhumäkiPetre2002b-6] Кархумяки, Юхани; Петре, Ион (2002). Подход к проблеме Конвея с использованием точки ветвления . Конспекты лекций по информатике. Том. 2300. стр. 69–76. дои : 10.1007/3-540-45711-9_5 . ISBN 978-3-540-43190-9 . ISSN 0302-9743 .

[Kunc2007-7] Кунц, Михал (2007). «Сила общения с конечным набором слов». Теория вычислительных систем . 40 (4): 521–551. дои : 10.1007/s00224-006-1321-z . ISSN 1432-4350 . S2CID 13406797 .

[Kunc2005-8] Кунц, Михал (2005). «Регулярные решения языковых неравенств и вполне квазипорядки» . Теоретическая информатика . 348 (2–3): 277–293. дои : 10.1016/j.tcs.2005.09.018 . ISSN 0304-3975 .

[ParikhChandra1985-9] Парих, Рохит; Чандра, Ашок; Халперн, Джо; Мейер, Альберт (1985). «Уравнения между обычными членами и приложение к логике процесса». SIAM Journal по вычислительной технике . 14 (4): 935–942. дои : 10.1137/0214066 . ISSN 0097-5397 .

[Okhotin2010-10] Охотин, Александр (2010). «Задачи решения языковых уравнений» . Журнал компьютерных и системных наук . 76 (3–4): 251–266. дои : 10.1016/j.jcss.2009.08.002 . ISSN 0022-0000 .

[Leiss1994-11] Лейсс, Э.Л. (1994). «Неограниченное дополнение в уравнениях языка в однобуквенном алфавите» . Теоретическая информатика . 132 (1–2): 71–84. дои : 10.1016/0304-3975(94)90227-5 . ISSN 0304-3975 .

[Jeż2008-12] Еж, Артур (2008). «Соединительные грамматики порождают нерегулярные унарные языки». Международный журнал основ компьютерных наук . 19 (3): 597–615. дои : 10.1142/S012905410800584X . ISSN 0129-0541 .

[JeżOkhotin2014-13] Еж, Артур; Охотин, Александр (2014). «Вычислительная полнота уравнений над множествами натуральных чисел». Информация и вычисления . 237 : 56–94. CiteSeerX 10.1.1.395.2250 . дои : 10.1016/j.ic.2014.05.001 . ISSN 0890-5401 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]