Computer Science 456/656: Automata and Formal Languages

Fall 1998

Homework Assignment, due October 15, 1998

You may discuss this assignment with other students in the class, or other persons.

• Work problem 6.1 on page 191 of your textbook. Answers.
• Work problem 6.12 on page 191 of your textbook. Answers.
• Work problem 6.17(g) on page 194 of your textbook. Answer.
• Work problem 6.43 on page 197 of your textbook. Answer.
• A CFG is "very simple" if the right hand side of every production is either the empty string, a single grammar symbol, or a terminal followed by a variable.
  • Prove that every language generated by a very simple grammar is regular. Answer.
  • Prove that every regular language that is accepted by an NFA-Lambda with n states is generated by a very simple grammar with n variables. Answer.