I want to construct a linear bounded automata for the language $L = \{a^nb^{2n} \mid n\geq1 \}$ . I know how LBA works but I don't have an idea how it can count the numbers of a's and check if the b's are 2 times more than a's. I would like to to hear some suggestions.


Repeatedly remove an $a$ from the beginning and a $bb$ from the end until the string becomes empty. If you cannot do it at any point, reject, otherwise, accept.

  • $\begingroup$ What do u mean ? I can only remove one character and only go one position to the right or left or to stay at the same position . So I start on the left side of the string remove one a go to the next character it can be another a or b $\endgroup$ Jun 25 '17 at 14:07
  • 1
    $\begingroup$ You have to be more creative. The algorithm I outlined can easily be implemented on an LBA. It seems you are confusing LBAs with DFAs. $\endgroup$ Jun 25 '17 at 14:21
  • $\begingroup$ so I begin with the first a and mark it as A' so I can know that this is the left end of the string then I should find the right end of the string b' , I find it and mark it as B' and I should go to the left and mark one more with Y then I should go to the left side or the first a which is unmarked and mark it with A and then again go to the right side and mark another 2 bs with B but then how can I check my string is complete marked ? $\endgroup$ Jun 25 '17 at 14:33
  • 2
    $\begingroup$ I'm sure you can figure it out. $\endgroup$ Jun 25 '17 at 14:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.