Skip to main content

Design a TM(Turing Machine) , L={a^nb^n | n>=1}

Design View:

By JFLAP Software


Concept : 

aaabbb
Case1: XaaYbb
Case2:XXaYYb
Case3:XXXYYY


Case 1:
Read first 'a' and replace it by 'X'
Then read first 'b' and replace it as 'Y'

What i am doing is .....Meaning of a^n b^n is " Equal no: of a's must followed by equal no: of b's "
In Case 1 : I read first 'a' and First 'b'.

Before reading Second 'b'....Should read Second 'a' ....

Then continue the steps.....Finally 'B' reads....Machine will stop...


Transitions concept will continue ......



Comments

  1. please tell me the turing machine for a^n+1 b^n

    ReplyDelete
    Replies
    1. make one state before q0(start state). and that state transited to q0 with a, B, R.
      is it problem solve or not?

      Delete
    2. plz turing machine for a^nb^n+1

      Delete
  2. V helpful .Thanks alot

    ReplyDelete
  3. thank you MR.ARUN ANOOP ou are real gentleman.

    ReplyDelete
  4. http://cs-09-506-toc.blogspot.in/2016/08/for-tution-theory-of-computation-please.html

    ReplyDelete

Post a Comment

Popular posts from this blog

PCP & MPCP

PCP(Post's Correspondence Problem)MPCP(Modified PCP)
PCP consists of two lists A=w1,....,wk and B=x1,....,xk , of strings over some alphabets SIGMA. This instance of PCP has a solution if there is any sequence of integers i1,i2,.....,im,with m>=1. Such that
wi1,wi2,....,wim=xi1,xi2,....,xim. The sequence i1,....,im is a solution to this instance of PCP.
MPCP  Lists A & B of k strings each from Sigma*.say A=w1,w2,...,wk and B=x1,x2,.....,xk does there exist a sequence of integers i1,i2,....,ir. such that w1 wi1 wi2 .... wir=x1 xi1 xi2 ..... xir ?
Difference between PCP and MPCP is that in the MPCP, a solution is required to start with the first string on each list.


Restricted Turing machine

1)Linear Bounded Automaton

2)Multi-stack Machines

3)Counter Machines

4)Limits on the number of states and symbols


Explanation: 
1)Linear Bounded Automaton:
       is a type of turing machine wherein the tape is not permitted to move off the portion of the tape containing the input. If the machine tries to move its head off either end of the input,the head stays where it is,in the same way that the head will not move off the left-hand end of an ordinary turing machine's tape.

     A Linear bounded automaton is a TM with a limited amount of memory. It can only solve problems requiring memory that can fit within the tape used for the input. Using a tape alphabet larger than the input alphabet allows the available memory to be increased up to a constant factor. 




2)Multi-stack Machines: 
       A deterministic two-stack machine is a deterministic TM with a read only input and two storage tapes. If a head moves left on either tape, a blank is printed on that tape.
Lemma: An arbitrary single tape …