Question

COMPUTER SCIENCE -- THEORY OF COMPUTATION

Please write a Turing-machine style of algorithm to decide the language L1 given below. Use specific, precise, step-by-step English.

Describe how to test whether or not an input string is in the language L1 in finite time. A state diagram is not necessary at all -- but optional and helpful.

L1 = {w : every ‘a’ within w is to the left of every ‘b’ within w} over the following alphabet
Σ = {a, b, c}. In other words, you’re not allowed to have any ‘b’ symbol to the left of any ‘a’.

Example strings: aaacbb ∈ L1 but cabca ∉ L1.

Answer 1

+

Input symbols = { a, b, c }

Tape symbols = { a, b, c, bl } (bl denotes blank)

The algorithm starts off with the head on the first letter of input w and state is q₀ (initial state).

Algorithm:

• If the tape symbol is a or c and state is q₀, move head/control to the right and don't change any state.
• If the tape symbol is b and the state is q₀, move head to the right and change state to q₁.
• If the tape symbol is b or c and the state is q₁, move head right and don't change state.
• If the tape symbol is a and the state is q₁, halt/stop executing as the input is not acceptable.
• If the tape symbol is bl and the state is q₁, don't move head and change state to q₂.
• If the tape symbol is bl and the state is q₂, halt.
• After halting, if the state is q₂ or q₀, the string is accepted by the machine else not.

State diagram:

a->a,R C->C,R b->b,R C->C,R b -> b,R bl -> bl,R 90 91

Here, a -> a,R means if a is encountered in tape, put a in it's place and move head Right.

In case of any doubt, drop a comment and I'll surely get back to you.

Please give a like if you're satisfied with the answer. Thank you.