GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
66 views
Is a^nb^3^n is CsL  or Recursive or Recursive enumerable?

Please draw the state transition diagram also

I think it is not any of them.because b^3^n I can't put in loop
asked in Theory of Computation by (43 points)  
reshown by | 66 views
I think its CSL that mean recursive language
But I cannot able to draw the state diagram.
we can determine the value of 3n by Linear bounded automata.
and count the number of a's and b's in the string.
Wrong..for 3n cfl enough.we dont need LBA

1 Answer

+1 vote
Is it 3n or 3^n?

If it is 3n then it can be a CFL but if it is 3^n then according to me it should be a Recursive Language.

Please correct me if I am wrong
answered by (143 points)  
it is 3^n...if it would have 3n then i would not have posted it..if recursive can you draw TM?


Top Users Sep 2017
  1. Habibkhan

    7092 Points

  2. Warrior

    2574 Points

  3. Arjun

    2408 Points

  4. rishu_darkshadow

    2402 Points

  5. A_i_$_h

    2204 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1760 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,114 questions
33,691 answers
79,841 comments
31,098 users