TOTAL POINTS 3
Construct a regular expression for each of the following languages over the binary alphabet or prove that no such regular expression is possible:
- All strings except 11 or 111.
- Strings with 1 in every odd-number bit position.
- Strings with an equal number of 0s and 1s.
- Strings with at least two 0s and at most one 1.
- Strings that when interpreted as a binary integer are a multiple of 3.
- Strings with no two consecutive 1s.
- Strings that are palindromes (same forwards and backwards).
- Strings with an equal number of substrings of the form 01 and 10.
Design a regular expressions of length nn such that any DFA that recognizes the same language has an exponential number of states.
Add to NFA.java(at booksite) the ability to handle multiway or, wildcard, and the + closure operator.
TOTAL POINTS 3
Generalize the Huffman algorithm to codewords over the ternary alphabet (0, 1, and 2) instead of the binary alphabet. That is, given a bytestream, find a prefix-free ternary code that uses as few trits (0s, 1s, and 2s) as possible. Prove that it yields optimal prefix-free ternary code.
1.Identify an optimal uniquely-decodable code that is neither prefix free nor suffix tree.
2.Identify two optimal prefix-free codes for the same input that have a different distribution of codeword lengths.
Design an algorithm to implement move-to-front encoding so that each operation takes logarithmic time in the worst case. That is, maintain alphabet of symbols in a list. A symbol is encoded as the number of symbols that precede it in the list. After encoding a symbol, move it to the front of the list.