Есть ли простой способ решения вопросов, связанных с созданием машины Тьюринга?

Я понял логику машины Тьюринга. Когда мне дают машину Тьюринга, я могу понять, как она работает и как останавливается. Но когда просят построить машину Тьюринга, это сложнее.

Есть ли простой способ найти ответ на такие вопросы, как:

Construct a Turing machine a*b* 
Construct a Turing machine a*b*a* 
etc.

Я хочу нарисовать эту машину Тьюринга? Есть ли какой-нибудь метод, например, заполнение таблицы, а затем ее построение и т. Д.?

Я много искал в Интернете по этой теме. Есть только ответы (только диаграммы). Нет объяснений, как это решается, как это нарисовано.

заранее спасибо


turing-machines formal-languages
person oiyio    schedule 25.08.2012    source источник
comment
Я не знал, что это такое. После того, как вы сказали, я искал и узнал это :) спасибо   -  person oiyio    schedule 26.08.2012

Ответы (1)


arrow_upward
0
arrow_downward

Два приведенных вами примера — это регулярные выражения, и действительно существуют простые алгоритмические способы превращения регулярных выражений в автоматы, а именно NFA. Когда у вас есть NFA, вы можете превратить их в TM, используя простую конструкцию.

Алгоритм превращения регулярных выражений в NFA выглядит следующим образом:

Правило 1: Если r = a для некоторого символа алфавита a, то NFA для r:

       a
--->q0--->(q1)

Правило 2. Если r = st для регулярных выражений s, t, а M1 и M2 являются NFA для s и t соответственно, то NFA для r будет следующим:

       e
--->M1--->M2

То есть начальным состоянием является состояние M1, допускающими состояниями являются состояния M2, и есть новые пустые переходы из всех (ранее) допускающих состояний M1 в (ранее) начальное состояние M2.

Правило 3: если r = s + t для регулярных выражений s, t, а M1 и M2 являются NFA для s и t соответственно, то NFA для r будет следующим:

       e
--->q0--->M1
     | e
     +--->M2

То есть начальным состоянием является новое состояние q0, конечными состояниями являются состояния M1 и M2, и добавляются два пустых перехода, ведущих из нового начального состояния в (ранее) начальные состояния M1 и M2.

Правило 4: Если r = s* для регулярного выражения s, а M является NFA для s, то NFA для r будет следующим:

     +------+
     |  e   |
     V      |
--->(q0)--->M

То есть добавляется новое начальное состояние q0, состояния принятия — это состояния M вместе с q0, и добавляются новые пустые переходы из состояний принятия M в q0.

В ваших примерах мы получаем NFA следующим образом:

a: Rule 1           a
             --->q0--->(q1)

b: Rule 1           b
             --->q0--->(q1)

a*: Rule 4         +-------------+
                   |      e      |
                   V             |
             --->(q0)--->q0'--->(q1)
                      e      a

b*: Rule 4         +-------------+
                   |      e      |
                   V             |
             --->(q0)--->q0'--->(q1)
                      e      b

a*b*: Rule 2      +-----------+
                  |           | e
                  V e      a  |
             --->q0--->q0'--->q1
                  |           |
                e |           | e
                  +-----------+--+
                  |              | e
                  V   e      b   |
                 (q2)--->q2'--->(q3)

a*b*: Rule 2      +-----------+
                  |           | e
                  V e      a  |
             --->q0--->q0'--->q1
                  |           |
                e |           | e
                  +-----------+
                  |           | e
                  V  e    b   |
                 q2--->q3'--->q3
                  |           |
                e |           | e
                  +-----------+--+
                  |              | e
                  V   e      a   |
                 (q4)--->q5'--->(q5)

Имея на руках NFA, TM можно построить следующим образом:

  1. Те же состояния, что и NFA
  2. Переходы, потребляющие ввод, перемещают головку ленты вправо.
  3. Пустые переходы вообще не двигают головку ленты.
  4. ТМ никогда не перезаписывает свой ввод.
  5. Когда TM встречает пустое место после достаточно далекого перемещения вправо, он переходит в состояние останова-принятия, если он находится в состоянии принятия для DFA, или в остановке-отклонении в противном случае.
person Patrick87    schedule 13.10.2017