This question is taken from an exam of a Computer Theory Course.

Describe how a NON-Deterministic Turing Machine with two tapes recognize the language generated from the grammar: $ S \rightarrow SS | (S) | )S( | \epsilon $.

  • Tape 1: Read-Only & monodirectional
  • Tape 2: Read and Write, bidirectional

My guess:

Example of string generated by this language: $w_1 = ()())($ $w_2 = )()($ $w_3 = )))((()($

I think that the Turing Machine should recognize strings such that for every open (close) parenthesis there is another close (open) one.

With non-determinism: I need to guess where a portion of string is generated by a valid production, but i have some troubles to formalize this concept. Any hints?

For the string $w_2$: One configuration in the computation tree would be $)(q_c)($ where $q_c$ identify the starting point of the production.

  • 1
    $\begingroup$ Hint: use the second tape to store the number $diff = \#_( - \#_)$; i.e. the (possibly negative) difference between the $($s and $)$s encountered so far. At each new symbol guess ... . At the end of the input check if $diff$ ... $\endgroup$
    – Vor
    Nov 2 '17 at 11:41
  • $\begingroup$ @Vor Do we have to guess at each new symbol? Just checking at the end would do? unambiguous grammar that produce equal number of a and b $\endgroup$ Nov 2 '17 at 14:40
  • $\begingroup$ @HendrikJan: you're right ... storing $diff$ seems powerful enough to make nondeterminism useless. $\endgroup$
    – Vor
    Nov 2 '17 at 16:06
  • $\begingroup$ Please state your question in the title ... this will be helpful for those searching for questions relevant to their own. $\endgroup$ Nov 2 '17 at 17:25
  • $\begingroup$ @HendrikJan I know that at the end, on the working tape should be written "0" but i can't figure out how precisely works the non-determinism here $\endgroup$
    – Jack
    Nov 7 '17 at 19:08

Your Answer

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

Browse other questions tagged or ask your own question.