Я освежал (не домашнее задание) некоторую теорию вычислений и столкнулся с этой проблемой:
Как вы можете доказать, что множество обычных языков является правильным подмножеством множества контекстно-свободных языков.
Теперь я знаю, что язык регулярен тогда и только тогда, когда он принимается конечным автоматом.
И я знаю, что язык является контекстно-свободным тогда и только тогда, когда он принимается выталкивающим автоматом.
Но я не уверен, какое решение.
Любой DFA эквивалентен PDA, который никогда ничего не помещает в свой стек, поэтому все обычные языки также являются контекстно-свободными. Более формально:
DFA определяется как 5-кортеж (Σ, S, s0, δ, F), состоящий из входного алфавита, набора состояний, начального состояния, таблицы переходов и набора конечных (принимающих) состояний.
PDA определяется как набор из 7 элементов, включающий все элементы DFA плюс два дополнительных параметра: Γ (алфавит стека) и Z (начальный символ стека). Таблица переходов PDA несколько отличается от таблицы переходов DFA: каждый переход может зависеть как от входного символа, так и от текущего символа стека, и переходы могут вытолкнуть или вытолкнуть из стека.
Таким образом, вводя фиктивный стековый алфавит, состоящий из одного символа, становится тривиальным (хотя несколько раздражающим и многословным для записи!) сопоставление таблицы переходов DFA (state, input) -> state с эквивалентной таблицей переходов PDA (state, input, stack) -> (state, stack).
Чтобы завершить доказательство правильного отношения подмножества: существуют языки, которые являются контекстно-свободными, но не регулярными, поэтому регулярные языки образуют правильное подмножество контекстно-свободных языков. Пример: язык строк, состоящий из сбалансированных скобок.
