CODEWITHSUNDEEP
automatafinite-automataautomata-theoryturing-machines
westman379
westman379

Reputation: 723

Design a turing machine that accepts the language L= {a^n+1 b^2n c^3n: n>=0}

I need some help with designing Turing machine that accepts language L= {a^n+1 b^2n c^3n: n>=0}

Upvotes: 1

Views: 4558

Answers (2)

Ahmad
Ahmad

Reputation: 126

Since we are not supposed to solve your homework :), I solved the following language on JFLAP and you can change it a little bit for your language. The logic is the same and you'd need to add a couple of states. L = {a^n+1 b^2n : n >= 0}

the solution on JFLAP

Upvotes: 1

Patrick87
Patrick87

Reputation: 28312

There are a lot of correct ways to do this. I will just walk through one of them I hope illustrates a useful way to attack these problems.

First, we notice the commonality n between the three segments. We will cross off symbols from each section, one at a time, to make sure they have the right relationships. First, we can verify that the relationship between a and b is right. Then, we can check the relationship between a and c. If those are both right, we are done.

First, let's get rid of the pesky "+1" from the a. This means we have at least one a regardless of what n is. So, we can begin by changing a to X. Now, the remaining input should have n instances of a, 2n instances of b and 3n instances of c. If we don't have the one a, we can halt-reject immediately; we can't have n+1 instances of a if we don't have at least one.

Now, if there are more instances of a, cross it off by writing A in its place, and go cross off two instances of b by writing B in their places. Then, go back and look for more instances of a, bouncing back and forth until there are no more instances of a. Then, verify there are no more instances of b; if so, there were twice as many instances of b as there were of a, and the first two sections have the right relationship. If at any point you didn't have enough b to cross off, or if after you ran out of a you still had b, then you can safely halt-reject at this point.

Next, you can do the same thing for instances of A and c, just cross off three instances of c instead of two. If we find the A get exhausted at the same time as the c do, we are done and halt-accept.

The transitions might look like this:

Q    T    Q'    T'    d        comment
q0   a    q1    X     right    account for +1

q1   a    q2    A     right    n>0 case, continue
q1   #    hA    #     same     n=0 case, accept

q2   a    q2    a     right    skip uncrossed a
q2   B    q2    B     right    skip crossed b
q2   b    q3    B     right    find first uncrossed b, cross it

q3   b    q4    B     left     find next b, cross it

q4   B    q4    B     left     find last uncrossed a
q4   a    q2    A     right    cross it
q4   A    q4    A     left     skip crossed a, if any
q4   X    q5    X     right    ran out of a to cross

q5   A    q5    A     right    skip crossed a
q5   B    q5    B     right    skip crossed b
q5   c    q6    c     left     verify existence of some c

q6   C    q6    C     left     skip crossed c
q6   B    q6    B     left     skip crossed b
q6   A    q7    a     right    find last crossed a, uncross
q6   X    q10   X     right    ran out of crossed a

q7   a    q7    a     right    skip uncrossed a
q7   B    q7    B     right    skip crossed b
q7   C    q7    C     right    skip crossed c
q7   c    q8    C     right    find first uncrossed c, cross
q8   c    q9    C     right    cross 2nd uncrossed c
q9   c    q6    C     left     cross 3rd uncrossed c

q10  a    q10   a     right    skip uncrossed a
q10  B    q10   B     right    skip crossed b
q10  C    q10   C     right    skip crossed c
q10  #    hA    #     same     accept if no leftover symbols until end

Upvotes: 1

Related Questions