Изменения
Нет описания правки
# Постройте КС-грамматику для языка $0^i1^j2^k$, $i \ne j$ или $j \ne k$.
# Постройте КС-грамматику для языка слов над алфавитом $\{0, 1\}$, которые не являются тандемными повторами.
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# задание на занятии
# Постройте автомат с магазинной памятью для языка слов, которые не являются правильной скобочной последовательностью.
# Постройте автомат с магазинной памятью для языка слов, которые не являются тандемными повторами.
# Постройте автомат с магазинной памятью для языка слов над алфавитом $\{0, 1, 2\}$, которые содержат равное число двоек и равное число единиц, или равное число двоек и равное число нулей.
# Существует ли для языка из предыдущего задания детерминированный автомат?
# Постройте автомат с магазинной памятью для языка палиндромов.
# Докажите, что для любого автомата с магазинной памятью существует эквивалентный, который на каждом переходе кладет в стек не более 2 символов. Ваша конструкция должна сохранять детерминированность автомата, если ранее он был детерминированным.
# Докажите, что для любого детерминированного автомата с магазинной памятью существует эквивалентный, который при $\varepsilon$-переходе только снимает или заменяет верхний символ стека (то есть размер стека не увеличивается на $\varepsilon$-переходах).
# Рассмотрим детерминированный автомат с магазинной памятью, для которого выполнены свойства из двух предыдущих заданий. Докажите, что для любого состояния $p$ автомата и строки $\gamma$ в стеке существует строка $s$, для которой выполняется следующее свойство. Начав в состоянии $p$ и со стеком $\gamma$, считав строку $s$ автомат переходит некоторое состояние $q$ и имеет в стеке $\beta$, причем какую бы строку далее автомат не получил на вход, на вершине стека никогда не окажется второй символ $\beta$.
# На основании трех предыдущих заданий докажите, что не существует детерминированного автомата с магазинной памятью для языка палиндромов.
</wikitex>
