при определении перехода CFG или грамматика типа 2 с КПК нам нужен начальный символ стека, чаще всего обозначаемый Zo. я сомневаюсь, зачем нам это нужно, потому что, в конце концов, мы вообще очистим стек....??
зачем автоматам с нажатием вниз нужен начальный символ стека?
Ответы (1)
Автоматам Pushdown нужен начальный символ стека, потому что каждый ход определяется текущим входным символом и тем, который находится на вершине стека. Это приводит к тому, что ход невозможен, если стек пуст.
И да, стек можно свести только к символу стека. Рассмотреть возможность...
L={ (a^n)(b^n) : n >= 0 }
Я мог бы нажимать 0 для каждого прочитанного a, который, кстати, первым из которых будет (q0, a, z), а затем, когда я прочитаю свой первый b, я выталкиваю 0 и ничего не возвращаю обратно. Я знаю, что я закончил, и язык принимается, когда ввод не используется, а символ стека находится поверх стека.
Обратите внимание, что в приведенной выше функции перехода первый ход определяется первым входом и символом стека. Вы видите, как без него вы никогда не сможете начать?
person
ChiefTwoPencils
schedule
10.04.2015
Что произойдет, если я нахожусь в состоянии
q0, а стек имеет z в качестве начального состояния. и я удаляю z из стека и перехожу к q1, я принял q1 как принимающее состояние. как вы сказали, если я дам больше входных данных для q1, это не будет принято, потому что теперь стек пуст.! а будет ли q1 принято или не принято .?
- person Jay Joshi; 02.12.2017
