# Non-deterministic Turing Machine recognizing a context-free Language

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.

• 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$ ... – Vor Nov 2 '17 at 11:41
• @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 – Hendrik Jan Nov 2 '17 at 14:40
• @HendrikJan: you're right ... storing $diff$ seems powerful enough to make nondeterminism useless. – Vor Nov 2 '17 at 16:06
• Please state your question in the title ... this will be helpful for those searching for questions relevant to their own. – reinierpost Nov 2 '17 at 17:25
• @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 – Jack Nov 7 '17 at 19:08