The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+4 votes
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 (73 points)
reshown by | 104 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

2 Answers

+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 (297 points)
it is 3^n...if it would have 3n then i would not have posted it..if recursive can you draw TM?
0 votes
It is recursive and i think it's belong to TM as a comparator in which (a<b) condition will satisfy.
answered by (311 points)

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

29,157 questions
36,984 answers
34,824 users