Turing machine for $a^i b^j$ with $i \geq j$

Question

I would have a brief question about how to construct a Turing machine that is accepting only this language:

$\qquad\displaystyle L_2 = \{a^i b^j \mid i \geq j \}$.

I can't come up with any mechanism that would preserve that there are greater or equal number of 'a's than 'b's. Could you suggest me something?

Answer 1

I concur with the Patrick87's suggestion, so here's my version of it.

For the notation in the state diagram, I've used a slightly lazy version, to hopefully reduce some the normal clutter a little.

1. The start state is marked with the $>$ (left side, in the middle), and I've included an explicit accept state (marked with the usual double circle and "Acc"), and an explicit reject state (marked "Rej").
2. The transitions are labelled $\alpha \rightarrow \beta,X$, where $\alpha$ is the symbol read from the current tape cell, $\beta$ is the (optional) symbol to write to the tape, and $X \in \{L,R,S\}$ is the direction to move the tape head - note that I've included $S$ as a "stay put" option, because it's a pain in the [expletive] if you have to move the head each time, but it doesn't really change anything.
3. I've also added some blue, numbered arrows to assist in the explanation below.
4. $\sqcup$ is the blank symbol.

Now, behold in all its glory, a Turing Machine (diagram):

Now, a couple of notes by way of explanation. Of course this is essentially Patrick87's suggestion as mentioned, so if you already get that, you don't need to read further. These correspond to the blue numbers in the image:

1. At each iteration of the basic loop (and in particular at the start) if the tape is blank, we move to the accept state, this corresponds to $i=j$ with the trivial case of $i=j=0$ if the tape is blank to start with.
2. If we see a $b$, then there must be too few $a$s, not that this also takes care of the situation where the $a$s and $b$s are out of order. This transition may make more conceptual sense after going through the main loop once, but it still applies at the start.
3. We read an $a$, and replace it with a blank - now we are on the hunt for either a matching $b$, or, if we've already used up all the $b$s, a blank at the end of the string of $a$s.
4. We also have constraints on the format of the string - all the $a$s must come before the $b$s, so to ensure this, we explicitly move past all the $a$s.
5. Once we've done that, if we see a blank, then there aren't any more $b$s, so we can accept (this is the $i > j$ case).
6. If we do see a $b$, then we'll match it with the $a$ we matched at step 3, but we want to take the last one (otherwise we would need to shuffle the string around, or use extra symbols to denote deletions that aren't blanks or something).
7. Once we hit the end of the string, we move back one, and take off the last $b$ (note that we had to have seen at least one $b$ to get here, so there's definitely one to remove).
8. Now we've matched an $a$ and a $b$, we can return to the start of the unprocessed string - just keep going until we hit a blank. Then we're in the same situation as when we started, just with two less characters in the string.

Answer 2

I would definitely go for Patrick87's approach, since it seems very natural to pair each a with a b (e.g. marking the letters) and analyze the cases you have when one of them (or both) runs out.

Then you can set a state to reject when, for a marked a, there is no b to pair out. And you would accept the input on all other cases.

Answer 3

q0 - start state

q4 - accpetance state

B - Blank symbol

Starting from q0 state the input head is at first 'a' on the tape. Explaining regarding the states

q0 : In this state when the input head sees 'a' it replaces with 'X' and moves right changing its state to q1. But if it sees b implying that there are more b's than a's which is not required denoted by moving to state q5 which is literally dead state.

q1 : In this state all a's and b's are left as it is moving right unless it encounters a Blank symbol 'B' or 'Y'(which is the replacement for 'b'). As it encounters 'B' or 'Y' it changes its state to q2 and start moving left of the tape in turing machine.

q2: In this state if it sees 'b' it replaces it with 'Y' and continue to move left and change it's state to q3, But if it sees 'a' denoting more number of a's and is one of the case of acceptance state and if it sees 'X' it denotes equal number of both which is the other case of acceptance.

q3: This state is similar in nature to q1 but it continues to move left unless it sees 'X' which is recent replacement for 'a' identifying that 'a' has been visited.

q4: As explained in q2, if q2 state sees either 'X' or 'a' move to acceptance state and here direction is unimportant.

q5: This state identifies if the input has more number of b's than a's. Here it is not required.