Как спроектировать автомат

Question

Как спроектировать автомат

Как бы я разработал КПК, который принимает сбалансированные скобки и скобки, например
([] []), Мне трудно начинать. Мне нужна помощь в написании функций перехода для этой проблемы. Любая помощь приветствуется

3

c++pushdown-automaton

Решение

Другие решения

Это может помочь вам начать:

bool check_and_pop(char c) {
if (top() == c) {
pop();
return true;
}
return false;
}

int check_input() {
char c;
while ((c = getc())) {
switch (c) {
case '(': case '{': case '[': push(c); break;
case ')':
if (!check_and_pop('(')
return REJECT;
break;
case '}':
if (!check_and_pop('{')
return REJECT;
break;
// ...
}
// end of input, check the stack to accept/reject
if (stack_size() == 0)
return ACCEPT;
else
return REJECT;
}

3

Источник

Accepted Answer

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

Давайте подумаем о том, как работает этот КПК, и пока забудем о состояниях и переходах, и еще много чего: когда наш КПК получает ввод, он должен работать так:

Если нет ввода:
- Если вершина стека пуста (на что часто указывает какое-то специальное значение, скажем, $ для этого примера) тогда наш КПК принимает строку: это правильно сбалансированная строка скобок и скобок.
- В противном случае мы переходим в состояние ошибки. Строка не является правильно сбалансированной строкой скобок и скобок.
Если вход является либо ( или [ затем поместите ввод в стек и посмотрите на следующий символ ввода.
Если вход является ) затем:
- Если вершина стека ( выдвиньте вершину стека и посмотрите на следующий ввод.
- В противном случае перейдите в состояние ошибки. Строка не является правильно сбалансированной строкой скобок и скобок.
Если вход является ] затем:
- Если вершина стека [ выскочить верхнюю часть состояния и посмотреть на следующий ввод.
- В противном случае перейдите в состояние ошибки. Строка не является правильно сбалансированной строкой скобок и скобок.

Теперь, зная, что должен делать наш КПК, давайте попробуем подумать о том, как описать наш КПК более формально. Мы будем предполагать, что:

Набор допустимых входных символов Σ = { (, ), [ а также ] }
Начальный стек символа Z = $
Набор допустимых символов стека Γ = { (, [ } ∪ Z
Множество состояний Q = {q0, ACCEPT, REJECT}
Начальное состояние q0.

Используя обозначения, похожие на то, что описано на http://en.wikipedia.org/wiki/Pushdown_automaton для переходов между состояниями КПК мы можем думать о состояниях и о том, как все происходит:

(q0, ε, top =$, ПРИНЯТЬ, ноль) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и больше нет ввода, а вершина стека является $ перейдите в состояние ПРИНЯТЬ, оставив стек без изменений.
(q0, ε, top =(, ОТКАЗ, ноль) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и больше нет ввода, а вершина стека является ( перейдите в состояние REJECT, оставив стек без изменений.
(q0, ε, top =[, ОТКАЗ, ноль) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и больше нет ввода, а вершина стека является [ перейдите в состояние REJECT, оставив стек без изменений.
(Q0, (, top = top, q0, push () Это говорит нашему КПК: когда вы находитесь в состоянии q0 и вход ( затем, независимо от того, что находится на вершине стека, перейдите в состояние q0 и нажмите ( в стек.
(Q0, [, top = top, q0, push [) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и вход [ затем, независимо от того, что находится на вершине стека, перейдите в состояние q0 и нажмите [ в стек.
(Q0, )сверху =(, q0, pop) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и вход ) и вершина стека ( затем перейдите в состояние q0 и снимите верхнюю часть стека.
(Q0, )сверху =[, ОТКАЗ, ноль) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и вход ) и вершина стека [ затем перейдите к стеку REJECT, оставив стек без изменений.
(Q0, )сверху =$, ОТКАЗ, ноль) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и вход ) и вершина стека $ затем перейдите к стеку REJECT, оставив стек без изменений.
(Q0, ]сверху =[, q0, pop) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и вход ] и вершина стека [ затем перейдите в состояние q0 и снимите верхнюю часть стека.
(Q0, ]сверху =(, ОТКАЗ, ноль) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и вход ] и вершина стека ( затем перейдите к стеку REJECT, оставив стек без изменений.
(Q0, ]сверху =$, ОТКАЗ, ноль) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и вход ] и вершина стека $ затем перейдите к стеку REJECT, оставив стек без изменений.

Мы могли бы добиться этого, используя больше состояний, но интересно отметить, что одного состояния «обработки» достаточно.

Вы также можете заметить, что в зависимости от вашего инструктора, вам может не потребоваться явно добавлять состояние REJECT, хотя это хорошая форма.

Надеюсь, это поможет.

9