Determine an unambiguous expression for the following sets of binary strings and then find their generating series as a rational function: a). Binary strings where there are never three or more 1's in a row. b). Non-empty binary strings in which the first and last entries are the same. You do not need to prove that your expressions are unambiguous.
Let \(\displaystyle {S_n}\) be the collection of all bit-strings of
length \(\displaystyle n\) that
do not contain the pattern \(\displaystyle 111\)
Here are the first three: \(\displaystyle \begin{array}{*{20}{c}}{{S_1}}\\0\\1\end{array}\) \(\displaystyle \begin{array}{*{20}{c}}{{S_2}}\\{00}\\{01}\\{10}\\{11}\end{array}\) \(\displaystyle \begin{array}{*{20}{c}}{{S_3}}\\{110}\\{101}\\{110}\\{011}\\{010}\\{001}\\{000}\end{array}\)
Now to get \(\displaystyle {S_4}\), we add \(\displaystyle 001\) to each string in \(\displaystyle {S_1}\); add \(\displaystyle 01\) to each string in \(\displaystyle {S_2}\); and add \(\displaystyle 0\) to each string in \(\displaystyle {S_3}\).
That gives \(\displaystyle \begin{array}{*{20}{c}}{{S_4}}\\{0001}\\{1001}\\{1101}\\{1001}\\{0101}\\{0001}\\{1100}\\{1010}\\{1100}\\{0110}\\{0100}\\{0010}\\{0000}\end{array}\)
You must take time to convince yourself that we found all of \(\displaystyle {S_4}\).
The number \(\displaystyle \left| {{S_4}} \right|\)\(\displaystyle = \left| {{S_1}} \right|\)\(\displaystyle + \left| {{S_2}} \right| + \left| {{S_3}} \right|\)\(\displaystyle =2+4+7=13\)
In general \(\displaystyle \left| {{S_n}} \right|\)\(\displaystyle = \left| {{S_{n-3}}} \right|\)\(\displaystyle + \left| {{S_{n-2}}} \right| + \left| {{S_{n-1}}} \right|\)
All your other questions done in that way. You just have to find the trick pattern.
