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.
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
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.
answered Jun 25, 2017 at 13:36
-
$\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$ Commented Jun 25, 2017 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$ Commented Jun 25, 2017 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$ Commented Jun 25, 2017 at 14:33
-
2$\begingroup$ I'm sure you can figure it out. $\endgroup$ Commented Jun 25, 2017 at 14:40