# Number of Configurations of LBA(Linear Bounded Automaton)

The lemma is:

Let $$M$$ be an LBA with $$q$$ states and $$g$$ symbols in the tape alphabet. There are exactly $$qng^n$$ distinct configurations of $$M$$ for a tape of length $$n$$.

I want know why LBA has $$qng^n$$ configurations.

Following is the proof:

A configuration of $$M$$ is like a snapshot in the middle of its computation. A configuration consists of the state of the control, position of the head, and contents of the tape. Here, $$M$$ has $$q$$ states. The length of its tape is $$n$$, so the head can be in one of $$n$$ positions, and $$g^n$$ possible strings of tape symbols appear on the tape. The product of these three quantities is the total number of different configurations of $$M$$ with a tape of length $$n$$.

• The proof you posted is OK, what is the question then? – diplodoc Aug 25 '19 at 10:05
• I can understand why there are g^n possible strings of tape. I cannot figure out the reasoning behind it – lemniscate Aug 25 '19 at 10:08

If you have $$g$$ symbols (including a blank) and a tape of size $$n$$ then there are $$g^n$$ words of length $$n$$. This is really basic combinatorics: The reasoning is that you have $$g$$ options for the first symbol, $$g$$ options for the second symbol, i.e. $$g^2$$ options for the first two symbols. Then again $$g$$ options for the third symbol, giving you $$g^3$$ options for the first three symbols and so on. If you are not convinced, try it with for example a $$3$$-symbol alphabet.
Since your tape has length $$n$$ there are $$n$$ possible head positions, so you multiply the number of strings on the tape with $$n$$.
Finally, there are $$q$$ states, so for every possible string on tape and every possible head position, we can be in either of the $$q$$ states, making $$qng^n$$ configurations of the Turing machine.