Какое из следующих утверждений является правильным?
- достаточные и необходимые условия о регулярности языка существуют, но еще не обнаружены.
Там нет достаточного и необходимого условия о регулярности языка.
Насосная лемма является необходимым условием нерегулярности языка.
- Насосная лемма является достаточным условием нерегулярности языка.
Я знаю, что # (4) является правильным, а # (3) ложным, потому что «обратное утверждение этого утверждения неверно: язык, удовлетворяющий этим условиям, все еще может быть нерегулярным», но что можно сказать о (1) и (2)?
Ответы:
Вот некоторые необходимые и достаточные условия для регулярности языка.
Теорема. Пусть . Следующие условия эквивалентны:L⊆Σ∗
Если язык никак не удовлетворяют условия насосных лемм для регулярных языков , то это не регулярно. Это означает , что насосная лемма является достаточным условием нерегулярности языка.
Таким образом, утверждение 1, 2 и 3 является ложным, а утверждение-верно, как вы упомянули.
источник
Достаточно (и необходимо) показать существование DFA, NFA или регулярного выражения, чтобы доказать, что язык является регулярным, что опровергает (1) и (2). Чтобы показать, что язык не является регулярным, необходимо показать, что DFA, NFA или регулярное выражение не существует.
Насосная лемма - полезный инструмент, чтобы показать (возможно, противоречие), что язык не является регулярным, показывая, что DFA не существует.
источник
Это условие не позволяет легко доказать нерегулярность языка. Я не знаю каких-либо условий, которые легко проверить, которые всегда доказывают нерегулярность нерегулярного языка.
Есть еще два «теста», которые могут доказать нерегулярность языка (хотя они могут не работать): вы можете попытаться дать некоторый обычный язык, такой, чтобы их объединение / пересечение / различие / конкатенация / частное было нерегулярным ( таких операций больше), и вы можете попытаться подсчитать, сколько слов он генерирует, и проверить, не противоречит ли оно выражению для количества слов на обычном языке (как можно найти на странице Википедии, на которую вы ссылались).
источник
Существует замечательная связь между теорией формального языка и формальными степенными рядами, доказанная Хомским и Шютценбергером [CS63] . В форме, найденной в [SS78] гл. II, теорема 5.1
[SS78] Арто Саломаа и Матти Соиттола. Автоматно-теоретические аспекты формальных степенных рядов. Springer-Verlag, Нью-Йорк, 1978.
[CS63] Ноам Хомский и Марсель П. Шютценбергер. Алгебраическая теория контекстно-свободных языков. В P. Braffort и D. Hirschberg, редакторы, Компьютерное программирование и формальные языки, стр. 118–161. Северная Голландия, 1963.
источник
источник