Regular languages

Define a floating-point number (a float) as consisting of a decimal point, with decimal digits on one or both sides of the decimal point. For example, 0.99, .25, and 100. are all floats. Floats (by this definition) have no sign and no exponent, but must have a decimal point and at least one digit.

1. Write a regular expression (as defined in this class, not as in a programming language) to describe floats.

2. Write a regular grammar to recognize/generate floats.

3. Create a set of MPCP dominos to implement the grammar for floats from the previous question.

4. Write a Turing Machine to recognize floats. The TM should start on the leftmost character of the input and end on the rightmost character of the input, in either a halting state named accept or one named reject. For brevity, you can use d to stand for any decimal digit.

Context free languages

1. Write a context-free grammar to recognize/generate palindromes over the alphabet {a, b, c}.

2. Create a set of MPCP dominos to implement the grammar for palindromes from the previous question.

3. Use the grammar from the first question above to derive a Turing Machine for palindromes.