# LBA for $L = \{a^nb^{2n} \mid n\geq1 \}$

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.

• 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 – Hans Christian Jun 25 '17 at 14:07
• 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. – Yuval Filmus Jun 25 '17 at 14:21
• 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 ? – Hans Christian Jun 25 '17 at 14:33
• I'm sure you can figure it out. – Yuval Filmus Jun 25 '17 at 14:40