Есть много способов доказать, что язык не является регулярным , но что мне нужно сделать, чтобы доказать, что какой-то язык является регулярным?
Например, если мне дано, что регулярно, как я могу доказать, что следующее регулярно?
Могу ли я нарисовать недетерминированный конечный автомат, чтобы доказать это?
Ответы:
Да, если вы можете придумать любое из следующего:
для некоторого языка тогда регулярно. Есть более эквивалентные модели , но вышеупомянутые являются наиболее распространенными.LL L
Есть также полезные свойства за пределами «вычислительного» мира. также регулярно, еслиL
Вы можете создать его, выполнив определенные операции на обычных языках, и эти операции закрыты для обычных языков , таких как
и более , или
В данном примере у нас есть некоторый (обычный) язык качестве основы и мы хотим сказать что-то о языке полученном из него. Следуя первому подходу - построить подходящую модель для - мы можем принять любую эквивалентную модель для мы так желаем; конечно, оно останется абстрактным, поскольку неизвестно. Во втором подходе мы можем напрямую использовать и применить к нему свойства замыкания, чтобы получить описание для .L ′ L ′ L L L L ′L L′ L′ L L L L′
источник
Элементарные методы
Логические методы (часто используемые при формальной проверке)
Продвинутые методы
Сложные насосные леммы. См., Например,
[1] Дж. Джаффе. Необходимая и достаточная лемма прокачки для обычных языков, Sigact News - SIGACT 10 (1978) 48-49.
[2] A. Ehrenfeucht, R. Parikh, G. Rozenberg, Леммы накачки для регулярных множеств, SIAM J. Comput. 10 (1981), 536-541.
[3] S. Varricchio, Условия накачки для регулярных множеств, SIAM J. Comput. 26 (1997) 764-771.
Ну квази-заказы. См.
[4] W. Bucher, A. Ehrenfeucht, D. Haussler, Об общих регуляторах, порожденных деривационными соотношениями, Theor. Вычи. Sci. 40 (1985) 131–148.
[5] М. Кунц. Регулярные решения языковых неравенств и квазипорядков скважин .
Поддержка -рациональных рядов.N
Алгебраические методы, основанные на преобразованиях (см. Также Операции, сохраняющие обычные языки ).
источник
Ответ Ранга Г. дает довольно обширный список эквивалентных моделей, которые можно использовать для определения обычных языков (и этот список можно продолжить, двусторонние автоматы, логика MSO, но это описано в разделе «более эквивалентные модели»). «). И, как подчеркивает Рафаэль, нам нужен аргумент, чтобы убедить аудиторию в том, что выбранное представление действительно правильно.
Пересматривая вопрос, он добавляет «Например, ». Это означает, что мы должны дать правильную конструкцию, которая, учитывая любую из вышеупомянутых моделей, которые мы предполагаем, задают язык , превращает эту модель в модель для . Как правило, это будет модель того же типа, но не обязательно: например, мы можем начать с детерминированного FSA для и закончить недетерминированным для .L L ′ L L ′… L L′ L L′
Это включает возможность использовать операции замыкания: в явно заданной операции в примере мы имеем .L′=(Σ∗∖L)⋅Σ∗
Итак, моя точка зрения такова, что ответ отличный, но мы должны добавить «от к конструкции, когда не строим определенный язык с нуля.L ′L L′
источник
<some property>
источник
источник
Язык является обычным, если вы можете написать сканер, который определяет произвольные строки независимо от того, принадлежат ли они языку или нет, используя не более фиксированного объема памяти - т.е. распознавание может быть выполнено в пространстве O (1) .
источник
Преобразование регулярных выражений является одним из способов доказать замыкание при определенных операциях. Двумя простейшими примерами являются замыкание при обращении и замыкание при гомоморфизме .
источник
Другой способ - создать язык, используя операции, под которыми вы знаете, что они закрыты. Это расширение для выставления регулярного выражения, поскольку у вас есть гораздо больше доступных операций (перевернуть строку, дополнить, пересечь, вырезать кусок, просто сохранить часть, гомоморфизмы и обратные гомоморфизмы, ...)
источник