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

ADVERTISEMENT

Get Answers For Free

Most questions answered within 1 hours.

ADVERTISEMENT

asked 7 minutes ago

asked 7 minutes ago

asked 8 minutes ago

asked 15 minutes ago

asked 21 minutes ago

asked 22 minutes ago

asked 23 minutes ago

asked 27 minutes ago

asked 27 minutes ago

asked 30 minutes ago

asked 36 minutes ago

asked 41 minutes ago