I want to construct a 2-tape Turing Machine, which decides in linear time if the input string over $\Sigma^* := \{(, [, ], )\}$ is a valid bracket.

I have not constructed too many TM's yet, this is why I need your help.

  • 2
    $\begingroup$ What is your question? What have you tried? Where did you get stuck? Do you have an idea how to check the valid brackets? (I assume it is about proper nesting, but this should be stated in your question). $\endgroup$ – Evil Jul 11 '17 at 17:34
  • $\begingroup$ Hint: use stack. Push '(' and '[' symbols, and pop them when you TM reads ']' and ')'. When you pop just check if symbols match (e.g. '(' with ')' and '[' with ']'). $\endgroup$ – fade2black Jul 11 '17 at 17:35
  • $\begingroup$ I saw identical question on this forum a couple weeks ago. I couldn't find it. @DavidRicherby or (CC: @D.W.) , I don't remember, one of them answered that question. $\endgroup$ – fade2black Jul 11 '17 at 17:39
  • 1
    $\begingroup$ How many tapes does your Turing machine have? With one tape it is impossible, with two tapes you can simulate a stack as in fade2black's comment. $\endgroup$ – Yuval Filmus Jul 11 '17 at 17:48
  • $\begingroup$ @fade2black TM is equipped with stack? Simply using search with "bracket" query there is cs.stackexchange.com/questions/11044/… $\endgroup$ – Evil Jul 11 '17 at 17:51

If you are not allowed to use two or more tapes then as Yuval Filmus commented you cannot solve in linear time. Otherwise you can convert the following steps into TM instructions:

 Initially input on the tape 1, the tape 2 is empty. 
 Machine reads input symbols stored on the tape 1, and tape 2 is used as stack (for push/pop operations). 

 1)  x = Read a symbol.
 2)  If x is '[' or '(' Then
 3)    push x and go to 1)
 4)  Else If x is ')' Then
 5)    sym = pop() 
 6)    If sym != '(' Then 
 7)       Reject and Halt.
 8)    Else
 9)       go to 1) 
 10) Else If x is ']' Then
 11    sym = pop()
 12)   If sym != '[' Then 
 13)      Reject and Halt.
 14)   Else
 15)      go to 1) 
 16) Else If x is '$' Then (if end of input)
 17)   If stack is empty Then
 18)      Accept and Halt
 19)   Else
 20)      Reject and Halt
 21) Else  
 22)   Reject and Halt

I think translation to a TM of this piece of code is quite tedious work.

In computability theory if you want to prove existence of a TM then informal description (or just description using one of the high-level programming languages) is enough. You may use a single tape TM model or multitape model. However, when dealing with time complexity selection of a model matters.

| cite | improve this answer | |
  • $\begingroup$ How do I see that the TM only needs linear time? $\endgroup$ – Pazu Jul 11 '17 at 19:22
  • $\begingroup$ Read-head scans the entire input only once (from left to right). If you have $n$ letter input it reads only $n$ times. As for Push and Pop, each Push/Pop operation takes $O(1)$ time, that is, only 1 step: just move the second head to the left (Pop) or move the head to the right and write a symbol (Push). In worst case when input, say, is '(((((((' the second head will move at most $n$ times to the right before it Rejects. $\endgroup$ – fade2black Jul 11 '17 at 19:26
  • $\begingroup$ Also note that each If-Then-Else also takes $O(1)$ time (one unit operation). $\endgroup$ – fade2black Jul 11 '17 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.