GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
68 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 | 68 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

    7166 Points

  2. Warrior

    2640 Points

  3. Arjun

    2574 Points

  4. rishu_darkshadow

    2520 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1846 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,144 questions
33,726 answers
79,957 comments
31,116 users