Chapter 8: Q7E (page 357)

Show that NL is closed under the operations union, concatenation, and star.

Short Answer

Expert verified

Step by step solution

Step-1:Class NL(Non-deterministic Logarithmic space)

On a non-deterministic Turing machine, NL is a class of languages that is decidable in logarithmic space.

Step-2- To Explain language by ML-machines

Take $B_{1}$ and $B_{2}$ to be languages determined by NL-machines $N_{1}$ and $N_{2}$ . Make three Turing machines: $N_{U}$ deciding $B_{1} \cup B_{2}$ and; $N_{O}$ deciding $B_{1} \circ B_{2}$ . $N_{*}$ deciding ${B_{1}}^{*}$ ..Each of these machines works in the following way.

1.The machine $N_{U}$ branches nondeterministically to simulate $N_{1}$ or to simulate $N_{2}$ . Accepts $N_{U}$ in either scenario if the simulated machine accepts.

2.To divide the input into two substrings, the machinechooses a nondeterministic place on the input. On the work tape, only a pointer to that spot is maintained because there isn't enough room to hold the substrings themselves. Then $N_{O}$ simulates $N_{1}$ nondeterminism on the first substring by branching nondeterministically. $N_{O}$ simulates $N_{2}$ on the second substring on any branch that reaches the accept state.

3.Machine $N_{*}$ has a more complex algorithm, so we describe its stages.

$N_{*}$ = “On input w:

Set two input position pointers $p_{1}$ and $p_{2}$ to 0 and the position immediately before the first input symbol.
Accept if no additional input symbols appear after $p_{2}$ .
Move $p_{2}$ to a nondeterministically chosen location.
To simulate $N_{1}' s$ nondeterminism, simulate $N_{1}$ on the substring of w from the location succeeding $p_{1}$ to the position at $p_{2}$ , branching nondeterministically.
Copy $p_{1}$ to $p_{1}$ and proceed to stage 2 if such a part of the simulation achieves $N_{1}' s$ approve state. Reject, if $N_{1}$ rejects on this branch.