1
Существует язык L = {0,1}^*, и дело в том, что 1 и 0 не должны иметь равное число. Как я могу представить это в автомате PDA?Автоматизация пускания с неравными элементами
Заранее благодарен!
A
ответ
1
КПК может считывать ввод, нажимать на стек и выталкивать стек. При попытке проектирования автоматов, особенно КПК и ТМ, мне нравится думать о входных строках в виде длинных рядов цветных мраморов или чипов, выстроенных на стол. Тогда возникает вопрос: как использовать только один стек и собирать чипы слева направо, можете ли вы сказать, имеет ли ряд чипов разное количество красных и синих фишек?
Один из способов заключается в следующем. Когда вы возьмете мрамор, посмотрите на стек. Если стек пуст или имеет тот же самый цветной чип сверху, поместите свой чип. Если самый верхний чип имеет другой цвет, бросьте чип, который вы собрали, и самый верхний чип из стека в сумку. Продолжайте, пока не возьмете все фишки. Теперь посмотрим на стек. Если стек пуст, это означает, что вы должны выбросить столько же красных и синих фишек. Если у вас есть фишки в стеке, значит, есть фишки, которые вы не могли выбросить. Действительно, цвет оставшихся чипов говорит о том, какой тип чипа был более многочисленным.