Question

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

Short answer

.

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}^{\ast }$..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\text{'}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\text{'}s$approve state. Reject, if $N_1$ rejects on this branch.