CIS-3030 Homework #3: Formal Languages

Due: Friday, November 1, 2013

Review the class notes on deterministic finite automatons, formal languages, context free grammars, and Turing machines. Don't forget that I also emailed you some notes (on DFAs) I wrote down during a recent lecture.

This is a review exercise to give you more practice with Haskell recursive functions. Write the following functions in Haskell using recursion (even if you see a way to use higher order functions instead):

        -- Return the number of times a particular integer occurs in a list.
        --
        -- For example: count 1 [0, 1, 2, 3, 2, 1, 0] should return 2.
        --
        count :: Int -> [Int] -> Int

        -- Return the binary representation of the given integer.
        --
        -- For example: toBinary 19 should return "10011". HINT: Use modulus to find out if
        -- the least significant digit should be "0" or "1" and then prepend onto that the
        -- result of converting the quotient to binary (after division by two).
        --
        toBinary :: Int -> String

        -- Split a list into a list of "small" values and a list of "large" values using the
        -- second parameter to define small and large values.
        --
        -- For example: partition [5, 7, 3, 9, 8, 8, 1] 5 should return ([5,3,1], [7,9,8,8]).
        -- The order of the elements in the returned lists does not matter.
        --
        partition :: [Int] -> ([Int], [Int])

The QuickSort algorithm works by partitioning a list into two lists of smaller and larger values and then invoking QuickSort recursively on the two sublists (and joining the results back together). For two bonus points, write QuickSort.

Consider the formal language over the alphabet { 0, 1, - } described by the grammar shown below.
```
        S -> S1 M S2
        S1 -> X | X S1
        S2 -> Y | Y S2
        M -> - M - | e
        X -> 1 0
        Y -> 0 1
      
```
Where S is the start symbol, { S, S1, S2, M, X, Y } is the set of non-terminals and e is the epsilon string (the string with no symbols). Note that the vertical bar is used to denote different alternatives in the productions.

Describe in words the nature of the strings in this language. Show an example of such a string consisting of at least six symbols and show the derivation of that string from the start symbol. What can you say about the length of the strings in the language generated by this grammar?
Slide #6 of the Turing machine slides on the class web site shows a sample Turing machine. The slide shows the initial tape contents of 1011. Does the sample machine accept or reject this input? What are the tape contents and head position after each transition made by the machine (until it halts)?

Note that the sample shows transitions labeled as (input, output, direction) where input is a slash delimited list of one or more input symbols that cause that transition to be taken, output is the output symbol written to the tape when that transition is taken, and direction is the direction the head moves when that transition is taken. Note also that any attempt to move the head off the left end of the tape just causes it to "bang" up against that end and not actually move.
A Turing machine is strictly more powerful than a deterministic finite automaton (DFA). This can be proved by showing how a Turing machine can simulate a DFA. Given a DFA as a collection of states with transitions between them as described in class, describe how you would construct a Turing machine program that will accept or reject a given input if and only if the DFA does.

HINT: Start with a Turing machine program using the same states as the DFA has. You'll need to adjust the transitions to handle the case of blank tape cells and to describe what to write to the tape and which direction to move the head.