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

Question

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

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

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

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

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

Answer 1

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

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

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

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

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