Достаточное и необходимое условие регулярности языка

11

Какое из следующих утверждений является правильным?

  1. достаточные и необходимые условия о регулярности языка существуют, но еще не обнаружены.
  2. Там нет достаточного и необходимого условия о регулярности языка.

  3. Насосная лемма является необходимым условием нерегулярности языка.

  4. Насосная лемма является достаточным условием нерегулярности языка.

Я знаю, что # (4) является правильным, а # (3) ложным, потому что «обратное утверждение этого утверждения неверно: язык, удовлетворяющий этим условиям, все еще может быть нерегулярным», но что можно сказать о (1) и (2)?

Gigili
источник
2
Скорее, я бы сказал, что (4) верно: лемма накачки предназначена для того, чтобы показать, что некоторый язык не является регулярным (в нем говорится, что L регулярна, то ...). Кроме того, (3) является ложным: en.wikipedia.org/wiki/…
jmad
Согласитесь с @jmad: лемма прокачки достаточна, не обязательна.
Patrick87
@jmad: В статье WP, на которую я ссылался в своем вопросе, говорится, что «и оригинальная, и общая версия леммы прокачки дают необходимое, но не достаточное условие регулярности языка».
Гигили
@ Джильи: да. Regular. Не "нерегулярно".
Джмад
@jmad: Ой, ты прав. Я отредактирую вопрос, спасибо.
Гигили

Ответы:

18

Вот некоторые необходимые и достаточные условия для регулярности языка.

Теорема. Пусть . Следующие условия эквивалентны:LΣ

  • генерируется регулярным выражением (т. Е. Определением регулярного языка).L
  • распознается недетерминированным конечным автоматом (Клини).L
  • распознается недетерминированным конечным автоматом без ε- переходов.Lε
  • распознается детерминированным конечным автоматом (Скотт и Рабин).L
  • порождается грамматикой ( N , Σ , P , S ) , где N - конечное подмножество Σ (Фрейзер и Пейдж).L(N,Σ,P,S)NΣ
  • генерируется левой (соответственно правой) регулярной контекстно-свободной грамматикой.L
  • Индекс отношения Нерода конечен (Анил Нероде, Линейные автоматные преобразования , 1958). Это широко (и неправильно) известно как теорема Майхилла-Нерода. L - отношение, используемое для построения минимального DFA обычного языка.LL
  • LL
  • LLL
  • L
  • L

Если язык никак не удовлетворяют условия насосных лемм для регулярных языков , то это не регулярно. Это означает , что насосная лемма является достаточным условием нерегулярности языка.

Таким образом, утверждение 1, 2 и 3 является ложным, а утверждение-верно, как вы упомянули.

Janoma
источник
ω
1
L
@AlextenBrink Забыл это! Спасибо за упоминание этого. У вас есть ссылки включить?
Janoma
@Janoma: извините, я не могу найти ни одного. Доказательство очень простое, хотя (собирается в NFA и обратно).
Алекс тен Бринк
9

Достаточно (и необходимо) показать существование DFA, NFA или регулярного выражения, чтобы доказать, что язык является регулярным, что опровергает (1) и (2). Чтобы показать, что язык не является регулярным, необходимо показать, что DFA, NFA или регулярное выражение не существует.

Насосная лемма - полезный инструмент, чтобы показать (возможно, противоречие), что язык не является регулярным, показывая, что DFA не существует.

Виктор Стафуса
источник
1
Лемма прокачки, технически говоря, показывает, что DFA не существует для языка.
Patrick87
@ Patrick87: Спасибо. Я отредактировал ответ, чтобы добавить эту деталь.
Виктор Стафуса
1
Просто для того, чтобы быть педантичным: доказательства, использующие лемму прокачки, не являются доказательствами от противоречия. Поскольку вы доказываете отрицательное утверждение (P -> False), с точки зрения интуициониста совершенно нормально предположить, что P имеет место.
Gallais
2
pwL
1
Вы можете написать его, но не нужно противоречие. В этом суть.
Janoma
6

LL

Это условие не позволяет легко доказать нерегулярность языка. Я не знаю каких-либо условий, которые легко проверить, которые всегда доказывают нерегулярность нерегулярного языка.

Есть еще два «теста», которые могут доказать нерегулярность языка (хотя они могут не работать): вы можете попытаться дать некоторый обычный язык, такой, чтобы их объединение / пересечение / различие / конкатенация / частное было нерегулярным ( таких операций больше), и вы можете попытаться подсчитать, сколько слов он генерирует, и проверить, не противоречит ли оно выражению для количества слов на обычном языке (как можно найти на странице Википедии, на которую вы ссылались).

Алекс тен Бринк
источник
6

Существует замечательная связь между теорией формального языка и формальными степенными рядами, доказанная Хомским и Шютценбергером [CS63] . В форме, найденной в [SS78] гл. II, теорема 5.1

LKchar(L)K

char(L)

[SS78] Арто Саломаа и Матти Соиттола. Автоматно-теоретические аспекты формальных степенных рядов. Springer-Verlag, Нью-Йорк, 1978.

[CS63] Ноам Хомский и Марсель П. Шютценбергер. Алгебраическая теория контекстно-свободных языков. В P. Braffort и D. Hirschberg, редакторы, Компьютерное программирование и формальные языки, стр. 118–161. Северная Голландия, 1963.

улы
источник
4

ILxyxILy

  1. zxxzxLyzxL
  2. zyyzyLxzyL

ILL

IL

Patrick87
источник