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
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.