Как доказать, что язык является регулярным?

48

Есть много способов доказать, что язык не является регулярным , но что мне нужно сделать, чтобы доказать, что какой-то язык является регулярным?

Например, если мне дано, что регулярно, как я могу доказать, что следующее регулярно?LL

L:={wL:uv=w for uΣL and vΣ+}

Могу ли я нарисовать недетерминированный конечный автомат, чтобы доказать это?

дерма
источник
1
есть опечатка в определении вашего , пожалуйста, исправьте, чтобы исправить. L
Ран Г.
2
«Рисование» не является доказательством; Вы должны дать NFA и доказать, что он принимает язык.
Рафаэль
Я думаю, что определение языка все еще не имеет смысла ...
hugomg
2
в любом случае, конкретный язык не имеет значения, если вопрос «могу ли я нарисовать NFA, чтобы доказать, что он регулярный». @corium, можем ли мы отредактировать вопрос, чтобы отразить более общий вопрос: «как доказать, что определенный является регулярным»? L
Ран Г.

Ответы:

48

Да, если вы можете придумать любое из следующего:

для некоторого языка тогда регулярно. Есть более эквивалентные модели , но вышеупомянутые являются наиболее распространенными.LLL

Есть также полезные свойства за пределами «вычислительного» мира. также регулярно, еслиL

  • это конечно,
  • Вы можете создать его, выполнив определенные операции на обычных языках, и эти операции закрыты для обычных языков , таких как

    • пересечение,
    • дополнение,
    • гомоморфизм,
    • реверс,
    • отношение слева или справа,
    • регулярная трансдукция

    и более , или

  • используя теорему Майхилла – Нерода, если число классов эквивалентности для конечно.L

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

Ран Г.
источник
4
Также стоит отметить, что доказательство языка конечно достаточно, чтобы показать его регулярность. Это может быть полезно, особенно в неконструктивных доказательствах в отдельных случаях.
Patrick87
2
Регулярные выражения в языках программирования могут делать гораздо больше, чем обычные языки. Вы должны ограничиться "классическими" конструкциями.
Дэвид Льюис
4
@DavidLewis: На этом сайте вы можете предположить, что под «регулярным выражением» подразумевается классическое понятие.
Рафаэль
@DavidLewis Я согласен, следует избегать «регулярных выражений» в контексте теории, чтобы избежать путаницы.
Рафаэль
Обратите внимание, что для любого из первых четырех пунктов вам понадобится доказательство того, что ваше представление действительно верно.
Рафаэль
10

Элементарные методы

  1. Конечные автоматы (возможно, недетерминированные, с пустыми переходами).
  2. Обычные выражения.
  3. Правые (или левые, но не оба) линейные уравнения, такие как где и регулярные.K LX=KX+LKL
  4. Обычная (тип 3) грамматика.
  5. Операции, сохраняющие обычные языки (булевы операции, произведение, звезда, случайное перемешивание, морфизмы, инверсии морфизмов, обращение и т. Д.)
  6. Распознается конечным моноидом.

Логические методы (часто используемые при формальной проверке)

  1. Монадическая логика второго порядка (теорема Бучи).
  2. Линейная временная логика (теорема Кэмпа).
  3. Теорема Рабина о дереве (монадическая логика второго порядка с двумя преемниками). Очень могущественный.

Продвинутые методы

  1. Сложные насосные леммы. См., Например,
    [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.

  2. Ну квази-заказы. См.
    [4] W. Bucher, A. Ehrenfeucht, D. Haussler, Об общих регуляторах, порожденных деривационными соотношениями, Theor. Вычи. Sci. 40 (1985) 131–148.
    [5] М. Кунц. Регулярные решения языковых неравенств и квазипорядков скважин .

  3. Поддержка -рациональных рядов.N

  4. Алгебраические методы, основанные на преобразованиях (см. Также Операции, сохраняющие обычные языки ).

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

Ответ Ранга Г. дает довольно обширный список эквивалентных моделей, которые можно использовать для определения обычных языков (и этот список можно продолжить, двусторонние автоматы, логика MSO, но это описано в разделе «более эквивалентные модели»). «). И, как подчеркивает Рафаэль, нам нужен аргумент, чтобы убедить аудиторию в том, что выбранное представление действительно правильно.

Пересматривая вопрос, он добавляет «Например, ». Это означает, что мы должны дать правильную конструкцию, которая, учитывая любую из вышеупомянутых моделей, которые мы предполагаем, задают язык , превращает эту модель в модель для . Как правило, это будет модель того же типа, но не обязательно: например, мы можем начать с детерминированного FSA для и закончить недетерминированным для .L L L L LLLL

Это включает возможность использовать операции замыкания: в явно заданной операции в примере мы имеем .L=(ΣL)Σ

Итак, моя точка зрения такова, что ответ отличный, но мы должны добавить «от к конструкции, когда не строим определенный язык с нуля.L LL

Хендрик Ян
источник
1
L
@ Рафаэль Извините, я сделал свою точку зрения. Ранние ответы, кажется, объясняют, что мы можем построить описание языка (как автомат, операции и т. Д.). Я согласен. Однако вопрос, похоже, касается свойств замыкания, см. Приведенный пример. Этот момент я упускаю в других ответах: чтобы доказать свойство замыкания, вы предполагаете, что у вас есть описание, и создаете новое.
Хендрик Янв
1
L
1
LLLLLLLLL
1
О хорошо На самом деле, я бы предпочел отредактировать вопрос и удалить часть «например», что сделало бы вопрос более общим и справочным материалом для будущих подобных вопросов .. (:
Ран Г.
4

L1SL2={x1y1xnynΣ:x1xnL1,y1ynL2}
Ai=Σ,Qi,Fi,δi,q0iLii=1,2Σ,Q,F,δ,q0
  • Q1×Q2×{1,2}xiyi
  • q0=q01,q02,1
  • F=F1×F2×{1}
  • δ(q1,q2,1,σ)=δ1(q1,σ),q2,2δ(q1,q2,2,σ)=q1,δ2(q2,σ),1

LR={wR:wΣ}.
(w1wn)R=wnw1LΣ,Q,F,δ,q0Σ,Q,F,δ,q0
  • Q=Q{q0}
  • q0
  • q0
  • δ(q0,ϵ)=FqQσΣδ(q,σ)={q:δ(q,σ)=q}

q0


R(L)={yxΣ:xyL}.
LΣ,Q,F,δ,q0Σ,Q,F,δ,q0q=δ(q0,x)δ(q,y)Fδ(q0,x)=qyx
  • Q={q0}Q×Q×{1,2}q0q,qcurr,sqqcurrsyx
  • F={q,q,2:qQ}δ(q0,x)=q
  • δ(q0,ϵ)={q,q,1:qQ}q
  • δ(q,qcurr,s,σ)=q,δ(qcurr,σ),sq,qcurrQs{1,2}
  • δ(q,qf,1,ϵ)=q,q0,2qQqfFyxy

Ek(L)={xΣ: there exists yL whose edit distance from x is at most k}.
Σ,Q,F,δ,q0LΣ,Q,F,δ,q0Ek(L)
  • Q=Q×{0,,k}
  • q0=q0,0
  • F=F×{0,,k}
  • q,σ,iδ(q,σ),iδ(q,i,σ)
  • q,i+1δ(q,i,σ)q,σ,ii<k
  • δ(q,σ),i+1δ(q,i,ϵ)q,σ,ii<k
  • δ(q,σ),i+1δ(q,i,τ)q,σ,τ,ii<k
Юваль Фильмус
источник
3

Язык является обычным, если вы можете написать сканер, который определяет произвольные строки независимо от того, принадлежат ли они языку или нет, используя не более фиксированного объема памяти - т.е. распознавание может быть выполнено в пространстве O (1) .

reinierpost
источник
O (1) пространство, ты имеешь в виду? В любом случае это связано с тем, что DFA достаточно; возможно, стоит явно отметить эту эквивалентность с точки зрения программирования.
Рафаэль
Да, это просто другая точка зрения.
reinierpost
3

Преобразование регулярных выражений является одним из способов доказать замыкание при определенных операциях. Двумя простейшими примерами являются замыкание при обращении и замыкание при гомоморфизме .

rLLRL

  • ϵR=ϵσR=σR=
  • (r1+r2)R=(r1R+r2R)(r)R=(rR)(r1r2)R=r2Rr1R

(r1r2)R=r2Rr1R(01)R=10rRLR

h:ΣΔrLh(L)σrh(σ)

Юваль Фильмус
источник
0

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

vonbrand
источник
2
Это уже упоминалось в ответе Рана.
Рафаэль