Создание всех контекстно-свободных языков из набора базовых языков и свойств замыкания?

10

Один из способов рассмотрения регулярных выражений - это конструктивное доказательство следующего факта: можно создавать регулярные языки, начиная с небольшого набора языков и комбинируя их с помощью небольшого фиксированного набора свойств замыкания. В частности, если мы начнем с пустого языка, языка, содержащего пустую строку, и языков всех односимвольных строк, мы можем собрать все возможные обычные языки, используя объединение, конкатенацию и звезду Клини.

Существует ли набор базовых языков и свойств замыкания, которые можно использовать для генерации всех и только контекстно-свободных языков? (Для пояснения: я не спрашиваю, можете ли вы писать регулярные выражения для всех CFL, что, как я знаю, невозможно. Вместо этого мне интересно, существует ли способ разработки структуры, подобной регулярному выражению для CFL, основанной на те же основные принципы.)

templatetypedef
источник
1
Как это происходит, один из наших справочных вопросов может содержать то, что вам нужно.
Рафаэль

Ответы:

8

Это возможно, но, возможно, не совсем так, как вы просите. В качестве начала возьмем язык Дейка из всех строк совпадающих скобок в двух парах скобок, скажем, или, более абстрактно, . { [ , ] , ( , ) } a 1 , b 1 , a 2 , b 2D2{[,],(,)}a1,b1,a2,b2

Тогда любой контекстно-свободный язык можно получить из используя гомоморфизмы, обратные гомоморфизмы и пересечение с регулярными языками. Свободные от контекста языки называются «главным конусом, порожденным », в старых книгах обозначались . См. Связанный вопрос: « Какие языки распознаются машинами с одним счетчиком? »D 2 M ( D 2 )D2D2M(D2)

На самом деле нам нужна только одна из каждой операции (правильно выбранная). Каждый CFL можно записать как , где , - гомоморфизмы, а - регулярный язык. Интуитивно понятно, что - это программа КПК, отображает каждую инструкцию на чтение буквы, на операции push и pop стека. Наконец, кодирует правильное поведение стека.g h R R g h D 2g(h1(D2)R)ghRRghD2

Этот результат связан с теоремой Хомского – Шютценбергера (или, как видно из википедии, одной из них). Утверждение, связанное здесь в википедии (а), не нуждается в обратном гомоморфизме, в то время как (б) оно не ограничивается двумя парами скобок. Теоремы этого типа взяты из области «Абстрактные семейства автоматов», где Гинзбург и Грайбах являются важными именами. Соответствующий результат Нивата утверждает, что операции вида для фиксированных являются преобразованиями конечного состояния.g , h , RLg(h1(L)R)g,h,R

Хендрик Ян
источник
Вау, это действительно интересно! Если у вас есть какие-либо ссылки на это, я хотел бы проверить их!
templatetypedef
Фантастический. Это прекрасно отвечает на мой вопрос.
templatetypedef