Докажите, что набор регулярных языков является надлежащим подмножеством набора языков без контекста.

Question

Я разбирался (не домашняя работа) с некоторой теорией вычислений и столкнулся с этой проблемой:

Как вы можете доказать, что набор регулярных языков является правильным подмножеством набора языков без контекста.

Теперь я знаю, что язык является регулярным, если он принят конечным автоматом.

И я знаю, что язык не зависит от контекста, если он принят нажатием автомат.

Но я не уверен, что такое решение.

Answer 1

Любой DFA эквивалентен PDA, который никогда ничего не помещает в свой стек, поэтому все обычные языки также не зависят от контекста.Более формально:

DFA определяется как 5-кортеж (Σ, S, s0, δ, F), состоящий из входного алфавита, набора состояний, начального состояния, таблицы переходов и набора конечных (принимаю) состояний.

КПК определяется как 7-кортеж, включая все элементы DFA, плюс два дополнительных параметра: Γ (алфавит стека) и Z (начальный символ стека).Таблица переходов PDA несколько отличается от таблицы переходов DFA: каждый переход может зависеть как от входного символа, так и от символа текущего стека, а переходы могут выталкивать или выталкивать из стека.

Итак, путем введения фиктивного стекаалфавит, состоящий из одного символа, тривиально (хотя и несколько раздражающе и долго не писать!) для сопоставления таблицы перехода DFA (state, input) -> state с эквивалентной таблицей переходов PDA (state, input, stack) -> (state, stack).

Чтобы завершить доказательство правильного отношения подмножества: существуют языки, которые не зависят от контекста, но не являются регулярными, поэтому обычные языки образуют надлежащее подмножество языков без контекста.Пример: язык строк, состоящий из сбалансированных скобок.