Один из способов рассмотрения регулярных выражений - это конструктивное доказательство следующего факта: можно создавать регулярные языки, начиная с небольшого набора языков и комбинируя их с помощью небольшого фиксированного набора свойств замыкания. В частности, если мы начнем с пустого языка, языка, содержащего пустую строку, и языков всех односимвольных строк, мы можем собрать все возможные обычные языки, используя объединение, конкатенацию и звезду Клини.
Существует ли набор базовых языков и свойств замыкания, которые можно использовать для генерации всех и только контекстно-свободных языков? (Для пояснения: я не спрашиваю, можете ли вы писать регулярные выражения для всех CFL, что, как я знаю, невозможно. Вместо этого мне интересно, существует ли способ разработки структуры, подобной регулярному выражению для CFL, основанной на те же основные принципы.)
источник
Ответы:
Это возможно, но, возможно, не совсем так, как вы просите. В качестве начала возьмем язык Дейка из всех строк совпадающих скобок в двух парах скобок, скажем, или, более абстрактно, . { [ , ] , ( , ) } a 1 , b 1 , a 2 , b 2D2 { [ , ] , ( , ) } a1, б1,2, б2
Тогда любой контекстно-свободный язык можно получить из используя гомоморфизмы, обратные гомоморфизмы и пересечение с регулярными языками. Свободные от контекста языки называются «главным конусом, порожденным », в старых книгах обозначались . См. Связанный вопрос: « Какие языки распознаются машинами с одним счетчиком? »D 2 M ( D 2 )D2 D2 M(D2)
На самом деле нам нужна только одна из каждой операции (правильно выбранная). Каждый CFL можно записать как , где , - гомоморфизмы, а - регулярный язык. Интуитивно понятно, что - это программа КПК, отображает каждую инструкцию на чтение буквы, на операции push и pop стека. Наконец, кодирует правильное поведение стека.g h R R g h D 2g(h−1(D2)∩R) g h R R g h D2
Этот результат связан с теоремой Хомского – Шютценбергера (или, как видно из википедии, одной из них). Утверждение, связанное здесь в википедии (а), не нуждается в обратном гомоморфизме, в то время как (б) оно не ограничивается двумя парами скобок. Теоремы этого типа взяты из области «Абстрактные семейства автоматов», где Гинзбург и Грайбах являются важными именами. Соответствующий результат Нивата утверждает, что операции вида для фиксированных являются преобразованиями конечного состояния.g , h , RL↦g(h−1(L)∩R) g,h,R
источник