Детерминистический конечный автомат против детерминированного автомата выталкивания

Мне было интересно, может ли кто-нибудь дать мне простое объяснение взаимосвязи между этими двумя терминами, так как меня очень смущает терминология.


language-agnostic dfa pushdown-automaton
person John Roberts    schedule 03.05.2013    source источник
comment
DFA — это конечный автомат, тогда как PDA — это стековый автомат. Какие аспекты терминологии смущают вас?   -  person RBarryYoung    schedule 03.05.2013
comment
stackoverflow.com/ вопросы/12164479/   -  person Josh Lee    schedule 03.05.2013

Ответы (1)


arrow_upward
5
arrow_downward

Детерминированный автомат проталкивания (DPDA) — это Детерминированный конечный автомат (DFA), который также имеет доступ к Stack, представляющий собой структуру данных "последний пришел, первый ушел" (LIFO).

Доступ к памяти позволяет DPDA распознавать большее количество строк, чем DFA. Например, для языка с символами A и B можно построить DFA для распознавания AB, AABB, AAABBB, но нельзя построить DFA для распознавания A^nB^n для всех n, в то время как это легко сделать с помощью DPDA. который работает следующим образом:

  1. Войдите в начальное состояние.
  2. Поместите $ в стек.
  3. Read letter from string.
    • if B, go to a terminal non-accept state.
    • если A, поместите A в стек и перейдите в состояние 4.
  4. Read a letter from string
    • if A, push A on the stack and stay in this state
    • if B, pop the top value from the stack.
      • If the popped value is A, go to state 5.
      • Если выскочившее значение равно $, перейдите в непринятое состояние терминала.
  5. Read a letter from string
    • if B, pop the top value from the stack.
      • If the popped value is A, stay in this state.
      • Если выскочившее значение равно $, перейдите в непринятое состояние терминала.
    • if we read the end of the string, pop the top value from the stack
      • If the popped value is $, go to the accept state
      • Если выскочившее значение равно A, перейдите в непринятое состояние терминала.
    • если мы читаем что-то еще из строки, переходим в терминальное непринятое состояние.

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

person pcurry    schedule 03.05.2013