Машина Тьюринга с двумя состояниями для сопоставления скобок

В колледже мы изучали теорию вычислений в целом и машины Тьюринга более конкретно. Одним из замечательных теоретических результатов является то, что за счет потенциально большого алфавита (символов) вы можете уменьшить количество состояний до 2.

Я искал примеры различных машин Тьюринга, и представлен общий пример - средство проверки / проверки скобок. По сути, он проверяет, (()()()))()()()сбалансирована ли строка скобок, например, (предыдущий пример вернул бы 0 для несбалансированного).

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

Просто чтобы уточнить, скобки «зажаты» между пустой лентой, поэтому в приведенном выше примере - - - - - - - (()()()))()()() - - - - - - -будет ввод на ленту. Алфавит будет включать в себя (, ), 1, 0, -, и *halt*государство не считается , как состояние.

Для справки у меня есть подход с тремя состояниями: Описание состояний:

 State s1: Looks for Closing parenthesis

 State s2: Looks for Open parenthesis

 State s3: Checks the tape to ensure everything is matched

 Symbols: ),(,X

Переходы, перечисленные как:

Action: State Symbol NewState WriteSymbol Motion

// Termination behavior
Action: s2 - *halt* 0  -
Action: s1 -  s3    -  r

//Transitions of TM
Action: s1 (  s1  (   l
Action: s1 )  s2  X  r
Action: s1 X  s1  X  l
Action: s2 ( s1 X  l
Action: s2 X  s2 X r
Action: s3 (  *halt* 0 -
Action: s3 X  s3     X r
Action: s3 -  *halt* 1 -

Прости неформальный способ записать все это. Я все еще изучаю теоретические конструкции, стоящие за этим.

_ ( ) [ { / \ $\_$

q0:  _ -> accept  // accept on empty string and on balanced parenthesis
     ( -> {,R,q1  // mark the first open "(" with "{" and goto q1
     ) -> reject  // reject if found unbalanced ")"
     \ -> /,L,q0  // go left
     / -> \,R,q0  // go right

q1:  ( -> [,R,q1  // replace "(" with "[" and continue ...
     ) -> /,L,q1  // ... until first ")", replace it with "/" and goto left
     [ -> \,R,q1  // found matching "(" bracket, goto right and search for another ")"
     _ -> reject  // no ")" found for the first "{", reject
     { -> \,R,q0  // this must be the last match, goto q0 and check if it is true
     \ -> /,L,q1  // go left
     / -> \,R,q1  // go right

Вы можете увидеть это на работе, используя онлайн-симулятор машины Тьюринга ; Исходный код:

0 _ Y r halt
0 ( { r 1
0 ) N r halt
0 \ / l 0
0 / \ r 0
1 ( [ r 1
1 ) / l 1
1 [ \ r 1
1 _ N r halt
1 { \ r 0
1 \ / l 1
1 / \ r 1

Последнее замечание: если вы хотите увидеть, как эта техника может быть доведена до предела, прочитайте (и попытайтесь понять :-) конструкцию универсальной машины Тьюринга с 2 состояниями и 18 символами Ю. Рогожина в «Малой универсальной Тьюринге». машины»

Тупой ответ: ваш результат обещает, что существует универсальная машина Тьюринга с двумя состояниями. Создайте любую TM для языка Dyck, вычислите его индекс и жестко закодируйте его в универсальный компьютер.

$\{\#,(,),x\}$$\hat{a}$$a$

• $q_0$

  $)$$a$$\hat{a}$$)$$\hat{x}$
  $)$$\#$$\hat{x}$$q_1$

  $\hat{(}$$\hat{(}$$x$
  $\hat{)}$$\#$

• $q_1$$\hat{(}^+$$\hat{x}$$\#$$\hat{x}$

1. $x$