EXERCISES ON FORMAL LANGUAGES AND MACHINES

READING 
-------
Notes for lectures 16 and 17.

EXERCISES
---------

 1. Characterize the language (set of strings) generated by the grammar:
      S := Ab
      A := bBa
      B := Ac
      A := b

 2. Is the language of Question 2 context-free?

 3. Give the parse tree that shows why a = b is an "expression" in C.

 4. Consider the grammar:
      S := Ab
      A := bBa
      B := Ac
      Aca := bA
      A := b
    Which of the following strings is not in the language generated by
    this grammar?
      bb  bbcab  bbbcacab  bbbbbbbb  bbbcacacacab  bbbbbcacab

 5. Show that the string 011001111 is in the language recognized by the 
    following nondeterministic FSA.








 6. Find a set of strings that is not in the language recognized by the 
    FSA in question 5.

 7. Give a deterministic FSA that recognizes the same language as
    the nondeterministic FSA in question 5.

 8. Draw a Turing machine that halts if and only if the input consists of
    just 1's, and the number of 1's is even.

 9. Draw a Turing machine that halts if and only if the input is an
    alternating sequence of 1's and 2's











.
.
.
.
.

	ANSWERS TO EXERCISES ON FORMAL LANGUAGES AND MACHINES

 1. bb, bbcab, bbbcacab, bbbbcacacab, bbbbbcacacacab, bbbbbbcacacacacab, ...
    Any string in the language must begin and end with a "b".  In between
    there is a string of k "b"s followed by k "ca"s for some k.

 2. The language is context-free because it can be generated by a context-free
    grammar.  In general, it's much easier to test if a *grammar* is context-
    free (check that it follows the rules) that to test if a *language* is
    (have to find a grammar or prove that none exists).  

 3. See Appendix A13 in K+R for the C grammar.

                             expression

                        assignment-expression

    unary-expression     assignment-operator     assignment-expression

   postfix-expression            =                  unary-expression

   primary-expression                              postfix-expression

      identifier                                   primary-expression

                                                      identifier

 4. bbbcacacacab.  There have to be more "b"s than "ca"s, not counting 
    the "b"s at the start and at the end.

 5. State transistions A -> A -> B -> A ->  A ->  A -> B -> B -> B -> B  

 6. Any string ending with 0 (and plenty of others, such as 110101).

 7. See slide 15.9 (note use of state 0 for "impossible")
                                           A  B       0  1
                                           ----       ----
                                           0  0    0  0  0
                                           0  1    1  0  3
                                           1  0    2  2  1
                                           1  1    3  2  3
    
 8.










 9.