Question

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

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

Algorithm to decide the language L1:

1.Let 'w' be the input string .

2.Put all the symbols of 'w' in the given order in an array and let 'n' be the number of symbols in the string and 'e' be the element to be scaned and 'i' be the location of the symbol.

3.Scan each symbol one by one to check whether 'b' is present in w or not.

4.If 'b' is present in w, find out the location of 'b'.

5. If e='b' at any location from i=0 to i=n-1,Run the loop from that i^th location to i=n to to check whether e='a' or not.

6.If so,then 'w' is not in the language L1,else 'w' is in the language L1.

I hope the given answer help you