$\begingroup$

The question and its answer is found in the following picture:

But I could not understand: 1- why we scan the input tape from left to right until a blank is encountered?

2- Also I could not understand why exactly one tape symbol receives a mark?

Could anyone explain this for me please?

Thanks!

$\endgroup$ 2

1 Answer

$\begingroup$

Let $A$ and $B$ be languages. A string $w$ is in the concatenation of $A$ and $B$ if you can write it as $w= ab$, where $a\in A$ and $b\in B$. This means that you can split $w$ into two halves. The first half is a string from $A$ and the second half is a string from $B$.

If you have two decideable languages $A$ and $B$, you can make a decider for $A$ concatenated with $B$ as follows:

Given a two-tape nondeterministic Turing machine,

1. Nondeterministically guess where to split the string into two parts $w=ab$.
2. Run the first machine to make sure the first half is in $A$. If it isn't, reject.
3. Run the second machine to make sure the second half is in $B$. If it isn't, reject.
4. If the string really is in the concatenation of $A$ and $B$, then one of these guesses will be correct; that nondeterministic branch will accept, so the computation itself accepts.

Everything else is just bookkeeping:

• "Read until you encounter a blank space" just means "Read the input until you reach the end of the input".
• "Mark just one of the symbols." This is a way to mark where you think the division $w=ab$ is.
• So, altogether these two instructions are: "Read each of the input characters, and nondeterministically decide where to divide the input into two parts by putting a mark where the division should happen."

$\endgroup$

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy