Question

Write a Turing-machine style of algorithm to decide the language L2 given below. Use specific, precise, step-by-step English. So, describe how to test whether or not an input string is in the language L2 in finite time. No need to write a state diagram.

L2 = {w : w has more a’s than it has b’s and c’s combined} over the alphabet Σ = {a, b, c}.

Example strings: abaca ∈ L2. bcaa ∉ L2.

Answer 1

(1)Convert for every a make a to X, make b to Y and make c to Z.

(2)Repeat the above process by moving the tape from left to right of the Turing machine until the blank symbol is found on both the ends.

(3)Remember for one iteration only one alphabet each of a,b,c is converted to X,Y ,Z.

(4) Now , at the final iteration there will be only a's will be left .

(5)If only a's are left and remaining all are X,Y,Z then take it to final state and accept the strong.

(6)If there are all X's and still b and c are remaining then the string is not accepted by the turing machine.