Counting sequences in a language or code. We consider a language or code with an

alphabet of n symbols $1,2,...,$ n$.$ A sentence is a finite sequence of symbols, k$1,...,$ km

where ki in $\{1,...,$ n$\}.$ A language or code consists of a set of sequences, which we will

call the allowable sequences.

A language is called Markov if the allowed sequences can be described by giving the

allowable transitions between consecutive symbols. For each symbol we give a set

of symbols which are allowed to follow the symbol. As a simple example, consider

a Markov language with three symbols $1,2,3.$ Symbol $1$ can be followed by $1$ or $3$;

symbol $2$ must be followed by $3$; and symbol $3$ can be followed by $1$ or $2.$ The sentence

$1132313$ is allowable $($i$.$e$.,$ in the language$)$; the sentence $1132312$ is not allowable $($i$.$e$.,$

not in the language$).$

To describe the allowed symbol transitions we can define a matrix A in Rn$$n by

Aij $=$

$\{1$ if symbol i is allowed to follow symbol j

$0$ if symbol i is not allowed to follow symbol j $.$

$($a$)$ Let B $=$ Ak$.$ Give an interpretation of Bij in terms of the language.

$($b$)$ Consider the Markov language with five symbols $1,2,3,4,5,$ and the following

transition rules:

$1$ must be followed by $2$ or $3$

$2$ must be followed by $2$ or $5$

$3$ must be followed by $1$

$4$ must be followed by $4$ or $2$ or $5$

$5$ must be followed by $1$ or $3$

Find the total number of allowed sentences of length $10.$ Compare this number to

the simple code that consists of all sequences from the alphabet $($i$.$e$.,$ all symbol

transitions are allowed$).$

In addition to giving the answer, you must explain how you solve the problem.

Do not hesitate to use Matlab.