Non-deterministic Turing Machine recognizing a context-free Language - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T06:59:04Z https://cs.stackexchange.com/feeds/question/83319 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/83319 1 Non-deterministic Turing Machine recognizing a context-free Language Jack https://cs.stackexchange.com/users/79611 2017-11-02T03:06:35Z 2017-11-03T00:43:22Z <p>This question is taken from an exam of a Computer Theory Course.</p> <blockquote> <p>Describe how a NON-Deterministic Turing Machine with two tapes recognize the language generated from the grammar: $S \rightarrow SS | (S) | )S( | \epsilon$.</p> </blockquote> <ul> <li>Tape 1: Read-Only &amp; monodirectional</li> <li>Tape 2: Read and Write, bidirectional</li> </ul> <p><strong>My guess:</strong></p> <p>Example of string generated by this language: $w_1 = ()())($ $w_2 = )()($ $w_3 = )))((()($</p> <p>I think that the Turing Machine should recognize strings such that for every open (close) parenthesis there is another close (open) one.</p> <p><em>With non-determinism</em>: 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?</p> <p>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.</p>