Identifying Sequences for Cellular Automata

Python 2: 93 byte

M,L,n=input();a=[]
while L:z=zip(L,L[1:]);a+=z;L=[M[i][j]for i,j in z]
print len(set(a))==n*n

Straightforward implementation: Find all pairs by zipping, memorize them for later and apply M to L. Repeat. Compare the number of unique pairs found.

Input is of the form [[0,1],[1,0]], [0,1,0,0], 2.

CJam, 53 43 42 bytes

l~:M;_,({_[\1>]zW<_{M\{=}/}%}*;](_*\L*_&,=

This is a very straight-forward implementation of the definition (I took some inspiration from Jakube after my first attempt). It expects input in reverse order on STDIN, using CJam-style arrays:

2 [1 0 1 1] [[0 1][1 0]]

Here is a test harness which runs the code against all inputs (converting them to the correct input format first). The results in the input field aren't actually used. Remove them if you don't trust me. ;)

Mathematica, 90 83 82 bytes

f=Length[Union@@Last@Reap[#2//.l_List:>Extract[#,Sow/@Partition[l+1,2,1]]]]==#3^2&

Another straight-forward implementation.

Usage:

f[{{0, 1}, {1, 0}}, {0, 1, 0, 0}, 2]

True