Computer Science 456/656: Automata and Formal Languages

Spring 2000

Homework Assignment 4.

Due March 8, 2000

You may discuss this assignment with other students in the class, or other persons. But you must actually write the assignment in your own hand. You must turn in the homework on letter-sized paper, with your name at the top of each page. Use pen or pencil, any color.

Do not write your homework as a computer file and turn in a printout.

• Work exercise 6.6 on page 192 of your textbook.
  There are two separate proofs required. You must prove that no string generated by the grammar contains the substring abb and you must also prove that, if w is any string over the alphabet which does not contain that substring, then w is generated by the grammar.
  Partial credit is available if you prove one but not the other.
• Work exercise 6.19 on page 194 of your textbook.
• Work exercise 6.22 on page 194 of your textbook.
• Work exercise 6.24 on page 194 of your textbook.
• Work exercise 6.27 on page 195 of your textbook.