Алгоритм проверки правильности языка

Существует ли алгоритм / систематическая процедура для проверки правильности языка?

Другими словами, учитывая язык , заданный в алгебраической форме (думаю , что - то вроде ), проверить , является ли регулярным или не язык. Представьте, что мы пишем веб-сервис, чтобы помочь студентам со всеми домашними заданиями; пользователь указывает язык, а веб-служба отвечает «обычный», «не обычный» или «я не знаю». (Мы бы хотели, чтобы веб-сервис отвечал «я не знаю» как можно реже.) Есть ли хороший подход к автоматизации этого? Является ли это послушный? Разрешаемо ли это (т. Е. Возможно ли гарантировать, что нам никогда не нужно отвечать «я не знаю»)? Существует достаточно эффективные алгоритмы для решения этой проблемы, и быть в состоянии дать ответ, кроме «не знает» $L=\{a^n b^n : n \in \mathbb{N}\}$

Классический метод для доказательства того, что язык не является правильным является накачка леммы. Тем не менее, похоже, что в какой-то момент требуется понимание вручную (например, чтобы выбрать слово для прокачки), поэтому мне не ясно, можно ли это превратить в нечто алгоритмическое.

Классический метод доказательства регулярности языка заключается в использовании теоремы Майхилла – Нерода для получения автомата конечного состояния. Это выглядит как многообещающий подход, но он требует умения выполнять основные операции на языках в алгебраической форме. Мне не ясно, существует ли систематический способ символически выполнять все необходимые операции над языками в алгебраической форме.

Чтобы сделать этот вопрос корректным, нам нужно решить, как пользователь будет указывать язык. Я открыт для предложений, но я имею в виду что-то вроде этого:

L знак равно {Е : S}

$L = \{E : S\}$

где - это слово-выражение, а - система линейных неравенств по переменным длины со следующими определениями: $E$ $S$

Каждый из является словом-выражением. (Они представляют переменные, которые могут принимать любое слово в .) $x,y,z,\dots$ $\Sigma^*$
Каждое из является словом-выражением. (Здесь представляет обратную строку .) $x^r,y^r,z^r,\dots$ $x^r$ $x$
Каждое из является словом-выражением. (Неявно, , поэтому представляют один символ в основном алфавите.) $a,b,c,\dots$ $\Sigma=\{a,b,c,\dots\}$ $a,b,c,\dots$
Каждое из является выражением слова, если является переменной длины. $a^\eta,b^\eta,c^\eta,\dots$ $\eta$
Конкатенация слов-выражений является словом-выражением.
Каждый из является переменной длины. (Они представляют переменные, которые могут принимать любое натуральное число.) $m,n,p,q,\dots$
Каждый из является переменной длины. (Они представляют длину соответствующего слова.) $|x|,|y|,|z|,\dots$

Это кажется достаточно широким, чтобы охватить многие случаи, которые мы видим в упражнениях из учебника. Конечно, вы можете заменить любой другой текстовый метод указания языка в алгебраической форме, если у вас есть лучшее предложение.

У меня еще не было времени много думать о вашем выборе языковых выражений. Примерно какие языки он охватывает? Если вы добавите ограничение, что переменная слова встречается только один раз, все ли эти языки не зависят от контекста?

Жиль "ТАК - перестань быть злым"

Может быть, вы можете попытаться написать сам с грамматикой? Как иэто кратко, что вы описываете?

E

$E$

E ::= c^{η} ∣ x ∣ E E ∣ E^{r}

$E ::= c^η ∣ x ∣ EE ∣ E^r$

η ::= n ∣ | x |

$η ::= n ∣ |x|$

Джмад

Вы можете выразить так что это выходит далеко за рамки контекстно-свободных языков. Тем не менее, я подозреваю, что проблема, по крайней мере, так же сложна, как решить, определяет ли контекстно-свободная грамматика обычный язык.

{a^{n} b^{n} c^{n} ∣ n \in N}

$\{a^nb^nc^n \mid n\in\mathbb{N}\}$

Жиль "ТАК - перестань быть злым"

@ jmad, да, это было бы совершенно разумно. Я не предан этому выбору языковых выражений: не стесняйтесь выбирать что-то другое, если вы видите что-то более подходящее. Жиль, отличный угол атаки! (Для зрителей известны результаты, показывающие, что проверка того, определяет ли произвольная неконтекстная грамматика обычный язык, неразрешима.) Если проблема неразрешима, я бы предложил настроить проблему, чтобы веб-служба отвечала: «Я не знаю не знаю ", а затем попросите алгоритм, который отвечает" я не знаю ", как можно реже.

Этот класс не закрыт под звездой Клини, не так ли? Можете ли вы выразить сбалансированные скобки?

Жиль "ТАК - перестань быть злым"

Ответы:

Ответ - нет. Решение о том, генерирует ли данная грамматика без контекста регулярный язык, является неразрешимой проблемой.

Обновление . Я дал этот отрицательный ответ на общий вопрос

Учитывая язык, указанный в алгебраической форме, проверьте, является ли язык регулярным или нет

поскольку контекстно-свободные языки являются решениями алгебраических уравнений в языках: см. главу II, теоремы 1.4 и 1.5 в книге Дж. Берстеля « Преобразования и контекстно-свободные языки» .

Тем не менее, тот же вопрос решаем для детерминированных контекстно-свободных языков, нетривиальный результат благодаря Stearns [1] и улучшен Valiant [2]:
[1] RE Stearns, Тест на регулярность для машин с нажатием кнопки, Информация и управление 11 323- 340 (1967). DOI: 10.1016 / S0019-9958 (67) 90591-8.
[2] LG Valiant. Регулярность и связанные с ней проблемы для детерминированных пуш-автоматов J. ACM 22 (1975), с. 1–10.

Есть еще один положительный результат, более близкий к спецификациям, приведенным во второй части вопроса. Напомним, что полулинейные подмножества - это в точности множества, определяемые в арифметике Пресбургера. Есть также рациональные подмножества . В частности, подмножество определяемое линейными уравнениями, рационально. Теперь, учитывая рациональное подмножество из , можно решить, является ли язык регулярно. Действительно, известно [Гинзбург-Спанье], что является регулярным тогда и только тогда, когда является распознаваемым подмножеством $\mathbb{N}^k$ $\mathbb{N}^k$ $\mathbb{N}^k$ $R$ $\mathbb{N}^k$

L (р) знак равно {U_{1}^{N_{1}} \dots U_{К}^{N_{К}} | (N_{1},,,,, N_{К}) \in р}

$L(R) = \{ u_1^{n_1} \dotsm u_k^{n_k} \mid (n_1, ...,n_k) \in R \}$

L (R)

$L(R)$

R

$R$

N^{k}

$\mathbb{N}^k$ и [Гинзбург-Спанье] решаемо, распознаваемо ли данное рациональное подмножество .

N^{k}

$\mathbb{N}^k$

S. Ginsburg, EH Spanier., Полугруппы, формулы Пресбургера и языки , Pacific J. Math. 16 (1966), 285-296.

С. Гинзбург и Э. Х. Спаниер. Ограниченные регулярные множества , учеб. американской математики. Soc. 17 , 1043–1049 (1966).

Это не решает вторую часть вопроса, которая может быть неразрешимой из-за слова переменные, но дает разумный фрагмент для начала.

J.-E. Штырь
источник

(а) педантичная нить: мне не ясно, является ли приведенный выше алгебраический синтаксис достаточно общим, чтобы выразить все контекстно-свободные грамматики (как мы с Жилем намекали в комментариях), поэтому не совсем ясно, применим ли этот конкретный результат здесь , (б) Более важно: пожалуйста, сочтите, что формулировка проблемы надлежащим образом настроена так, чтобы веб-сервису разрешалось отвечать «Я не знаю», и мы хотели бы найти алгоритм, который отвечает «Я не знаю» так редко насколько это возможно. Ранее я предложил это в комментариях; Я отредактирую вопрос, чтобы сделать это более понятным в самом вопросе.

Я подозреваю, что вы можете адаптировать доказательства, но результат не следует. Я думаю, что существуют контекстно-свободные языки, которые не могут быть выражены в этом формализме: например, как вы выражаете сбалансированные скобки? Класс языков не закрыт под звездой Клини, не так ли?

Жиль "ТАК - перестань быть злым"

@ Жиль, да, я думал об этом. Мне не сразу понятно, как адаптировать доказательство. Стандартное доказательство того, что неразрешимая грамматика без контекста неразрешимо, - это теорема Грейбаха. Однако мне не кажется, что этот класс языков удовлетворяет условиям теоремы Грейбаха (он вряд ли будет закрыт при конкатенации с регулярными наборами и закрыт при объединении). Может быть, есть какой-то другой доказательный подход, с которым я не знаком. Я согласен, не ясно, как выразить язык сбалансированных скобок в этой алгебраической форме.

Просто добавил ссылки.

Ж.-Е.

Ваш пост не отвечает на вопрос, потому что он затрагивает другой класс языков. Допустимые здесь алгебраические формы (с одним выражением слова) (насколько мы можем судить) не настолько общие, как алгебраические формы, необходимые для выражения произвольных контекстно-свободных языков. Может случиться так, что для пересечения двух, проблема разрешима.

Жиль "ТАК - перестань быть злым"