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

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

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

Гинзбург и Рис^[1]дал альтернативное определение контекстно-свободные грамматики языковыми уравнениями. К каждой контекстно-свободной грамматике ${displaystyle G = (V, Sigma, R, S)}$, связана система уравнений от переменных ${displaystyle V}$. Каждая переменная ${displaystyle Xin V}$ неизвестный язык ${displaystyle Sigma}$ и определяется уравнением ${displaystyle X = alpha _ {1} чашка ldots чашка 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}) чашка {b} чашка 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} чашка 0cdot S_ {2} чашка {epsilon}}$, ${displaystyle S_ {2} = 1cdot S_ {2} чашка 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] доказал, что каждый рекурсивный унарный язык является единственным решением некоторого уравнения.

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

• Логическая грамматика
• Правило Ардена
• Установить ограничение

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

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

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

Этот теория множеств -связанная статья является заглушка. Вы можете помочь Википедии расширяя это.