I need to create a turing machine that accepts the language $a^ib^jc^k$ where $i \ge j \ge k$, but I am not even really sure how to start. Turing machines in this context are a hard concept for me to grasp for some reason.


One idea is to delete characters, to make it easier let me introduce @ character - it will denote empty space after scratching characters.
For example let input string be $BaabccB$, where $B$ is blank symbol.
At first check for $a$ and create state, say $qa$ which looks for $a$ and then replaces it with $@$ switches to $qb$ moves right until it finds $b$.
Then it replaces $b$ with $@$ switches state to $qc$ and moves right until it finds $c$.
Here again replaces $c$ with $@$ and switches to state $ql$ moves to the left until $a$ is found.
While moving right if blank symbol is encountered, it means that there are less symbols of particular character, this is good according to given language, if the next character is also missing otherwise it breaks inequality and we reject. Also when we seek $b$ but encounter $c$ we reject. After consecutive $c$ if there are other symbols, we reject (it is something like $abca$
When moving left, when blank is encountered, we are finished and accept.

It may happen that there are not sufficient number of $a$ or any character, so after reaching blank character we move right to delete $@$ characters. If we clear all and hit blank, we accept, otherwise we reject as some characters broke inequality.

Example: $BaabccB$
$B@abccB$ move right, switch state, replace $b$
$B@a@ccB$ move right, switch state, switch $c$.
$B@a@@cB$ move left until $a$ replace
$B@@@@cB$ move right, switch state, $c$ is encountered in $qb$ state, it means that $#c > #b$ reject.

Excersise 1:
Try to solve similar question where $i \ge j \le k$

Excersise 2:
Try to solve similar question where $i = 2j = 3k$

| cite | improve this answer | |

There are two things you need to do when designing a Turing machine (or, in fact, writing any computer program). The first is to decide what algorithm you're going to use, and the second is to express that as a Turing machine/Java program/whatever. I'll cover the first part.

Turing machines were inspired by what a human could compute using a pencil and paper so, usually, the best way to figure out an algorithm is to think, "How would I do this if somebody gave me a really long string written on a piece of paper and asked me to determine if the string is in the language?" First, you'd scan the input to check that it really is a bunch of $a$s followed by a bunch of $b$s followed by a bunch of $c$s. Then what?

  1. You could count the $a$s, $b$s and $c$s, call those numbers $i$, $j$ and $k$, and check that $i\geq j\geq k$. That's all very well but the numbers are big so you'll lose count unless you write down the numbers step by step. As in, there are $1$, $2$, $3$, ..., $45\,387\,298$ $a$s. And then you need to figure out how to compare if one number is bigger than another and this is all rather tricky and tedious.

  2. You don't actually care what the numbers are, as long as they're in the right pattern, so why bother computing them at all? If you had a big pile of stones and you wanted to know if it was an odd or even number, you could count, or you could just arrange the stones into pairs and see if there's one left over. The same idea applies here: go through the string and repeatedly cross out an $a$, a $b$ and a $c$. If you run out of $c$s first, there are more $a$s and $b$s than $c$s. Then cross out $a$s and $b$s and check that you run out of $b$s next. What is "crossing out"? Well, looking at it kinda literally, you're replacing a character $a$ with $\not{\!a}$, etc., and you can always add $\not{\!a}$, $\not{b}$ and $\not{\!c}$ to your alphabet. Or you can make your life easier by interpreting "cross out" as "replace with $\times$" since, once a character is crossed out, you don't actually care what it used to be.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.