Существует ли расширение регулярных выражений, которое фиксирует языки без контекста?

25

Во многих работах с использованием контекстно-свободных грамматик (CFG) примеры таких грамматик, представленные там, часто допускают простую характеристику языка, который они генерируют. Например:

SaaSb
S

генерирует {a2ibi|i0} ,

SaSb
SaaSb
S

генерирует {aibjij0} и

SaSa
SbSb
S

генерирует {wwRw(a|b)} или эквивалентно {((a|b))1((a|b))2p1=p2R} (где p1 обозначает к той части , захваченной (...)1 ).

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

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

Алекс тен Бринк
источник
3
Заметьте, что добавление индексов и ограничений слишком сильно: вы сможете определить , который не является CFL. anbncn
Шауль

Ответы:

34

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

g::=ϵEmpty string|cCharacter c in alphabet Σ|ggConcatenation|Failing pattern|ggDisjunction|μα.gRecursive grammar expression|αVariable expression

Это все конструкторы для регулярных языков, за исключением звезды Клини, которая заменяется общим оператором с фиксированной точкой μα.ggμα.ϵgα

Интерпретация выражения без контекста требует учета интерпретации свободных переменных. Поэтому определите окружение которое будет отображаться из переменных в языки (то есть подмножества ), и пусть будет функцией, которая ведет себя как на всех входах, кроме и который возвращает язык для .ρΣ[ρ|α:L]ραLα

Теперь определим интерпретацию выражения без контекста следующим образом:

[[ϵ]]ρ={ϵ}[[c]]ρ={c}[[g1g2]]ρ={w1w2|w1[[g1]]ρw2[[g2]]ρ}[[]]ρ=[[g1g2]]ρ=[[g1]]ρ[[g2]]ρ[[α]]ρ=ρ(α)[[μα.g]]ρ=nNLnwhereL0=Ln+1=Ln[[g]][ρ|α:Ln]

Используя теорему Кнастера-Тарского, легко увидеть, что интерпретация является наименее фиксированной из выражения.μα.g

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

РЕДАКТИРОВАТЬ: Нет, я не знаю стандартную ссылку для этого: я разработал его для своих собственных интересов. Тем не менее, это достаточно очевидная конструкция, которая, я уверен, была изобретена ранее. Некоторые случайные поиски в Google показывают Joost Winter, недавнюю статью Marcello Bonsangue и Jan Rutten Context-Free Languages, Coalgebraically , где они дают вариант этого определения (требующий защиты всех фиксированных точек), который они также называют выражениями без контекста.

Нил Кришнасвами
источник
Это довольно круто. Есть ли стандартное имя или ссылка для этого?
Алекс тен Бринк
5
Арто Саломаа освещает это в своей книге «Формальные языки» в 1973 году. Он называет их «регулярными выражениями».
Тим Шеффер
3

На MathOverflow был тесно связанный вопрос (и несколько ответов) о языках, производящие функции которых голономны .

Интересно, что определение Нилом семантики выше точно соответствует (конструктивному) доказательству существования видовых решений рекурсивных уравнений вида через неявную теорему о видах. К сожалению, его схема доказательства также должна содержать тонкую ошибку, так как есть случаи, когда дела идут «бесконечно». Другими словами, на якобиане существует условие преобразования, определяемого грамматикой, чтобы оно было неособым, что необходимо. Вероятно, именно поэтому Бонсанге-Руттен требует, чтобы фиксированные точки были защищены, как один из способов обеспечить это условие на якобиане.μ

Жак Каретт
источник
AFAICT, Winter и др. Требуют только осторожности, чтобы гарантировать, что вы можете взять производную Бжозовского , взяв производную . [ μ α .μα.g[μα.g/α]g
Нил Кришнасвами
1

Недавно мы опубликовали наброски структуры, которая будет делать именно это. Посмотрите в comp.compilers , куда я отправил уведомление вместе с некоторыми ссылками.

Новые разработки основаны на теореме Хомского-Шютценбергера и могут рассматриваться как завершение этого результата. Сам Хомский был проинформирован о событиях и указывает на желание «наверстать упущенное».

Наряду с этим развитием мы также устанавливаем эквивалентность двух отдельных формулировок для выражений без контекста - одна, которая является расширением / дополнением формы мю-исчисления с «наименьшей фиксированной точкой» (первоначально Gruska, Yntema и McWhirter) - который получил окончательный вид сортов в 2014 году, а другой опубликован в 2008 году.

NinjaDarth
источник
4
Пожалуйста, включите всю соответствующую информацию в самом ответе. «Смотрите под comp.compilers» уже сейчас бесполезный ответ, и через пару месяцев он будет совершенно бесполезен.
Эмиль Йержабек поддерживает Монику
Это совершенно неправильно. Comp.compilers (кстати, в отличие от этого сайта и других блогов) постоянно архивируется. Там вы найдете все детали, которые вам нужны. Там можно найти много ссылок, в том числе в самой последней опубликованной статье. Кроме того, в отличие от блоговых сайтов, он открыт для внешних пользователей и полезен для гораздо более широкой аудитории. У вас не должно возникнуть никаких проблем с поиском чего-либо в USENET - именно здесь такие вопросы следует адресовать и обсуждать. Если у вас возникли трудности, вот ссылка. groups.google.com/forum/#!topic/comp.compilers/YCa5jHUR1iQ
NinjaDarth
2
Проблема не в том, что он не заархивирован, а в том, что архивы огромны. Когда я смотрю архивы Теперь я могу найти свой пост где - то около вершины, но когда кто - то увидит этот ответ через несколько месяцев или лет в будущее, они не будут иметь ни малейшего представления , с чего начать копать. Высокомерно и грубо заставлять читателей делать длительный и ненадежный поиск, когда вы можете указать им более конкретное местоположение. Теперь я сделал это для тебя. Это заняло около 30 секунд. Ты мог бы сделать это сам.
Эмиль Йержабек поддерживает Монику