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

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

Источник

2 ответа

Решение

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

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

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

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

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

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

  • (q0, ε, top = $ , ПРИНЯТЬ, ноль) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и больше нет ввода, а вершина стека является $ перейдите в состояние ПРИНЯТЬ, оставив стек без изменений.

  • (q0, ε, top = ( , REJECT, nil) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и больше нет ввода, а вершина стека является ( перейдите в состояние REJECT, оставив стек без изменений.

  • (q0, ε, top = [ , REJECT, nil) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и больше нет ввода, а вершина стека является [ перейдите в состояние REJECT, оставив стек без изменений.

  • (q0, ( , top = top, q0, push ( ) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и вход ( затем, независимо от того, что находится на вершине стека, перейдите в состояние q0 и нажмите ( в стек.

  • (q0, [ , top = top, q0, push [ ) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и вход [ затем, независимо от того, что находится на вершине стека, перейдите в состояние q0 и нажмите [ в стек.

  • (q0, ) сверху = ( , q0, pop) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и на входе ) и вершина стека ( затем перейдите в состояние q0 и снимите верхнюю часть стека.

  • (q0, ) сверху = [ , REJECT, nil) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и на входе ) и вершина стека [ затем перейдите к стеку REJECT, оставив стек без изменений.

  • (q0, ) сверху = $ , REJECT, nil) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и на входе ) и вершина стека $ затем перейдите к стеку REJECT, оставив стек без изменений.

  • (q0, ] сверху = [ , q0, pop) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и на входе ] и вершина стека [ затем перейдите в состояние q0 и снимите верхнюю часть стека.

  • (q0, ] сверху = ( , REJECT, nil) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и на входе ] и вершина стека ( затем перейдите к стеку REJECT, оставив стек без изменений.

  • (q0, ] сверху = $ , REJECT, nil) Это говорит нашему КПК: когда вы находитесь в состоянии q0 и на входе ] и вершина стека $ затем перейдите к стеку REJECT, оставив стек без изменений.

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

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

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

Источник

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

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;
}
Источник
Другие вопросы по тегам