 |
The Theory of Computation | Bernard M.E. Moret |
|
SOLUTION MANUAL: CHAPTER 3
Solutions are given here to all of the exercises in Chapter 3 of the text
as well as to all of the additional problems for that chapter.
Because most of these solutions require a fair amount of notation, the first
version of this solution manual provides only Postscript files. In the near
future, an HTML version should be available, but it will require Netscape
with some modifications in order to be readable, since mathematics support
remains minimal under HTML.
Exercises from the text are referred to by their number; additional exercises
use numbers matching those given in the list of additional exercises.
For convenience, each entry below also gives a few keywords for each exercise
to help in locating a specific exercise.
Files use plain fonts (Computer Modern) and formatting rather than the fonts
and format of the text and so are small for fast downloading.
Text Exercises
-
within the text
- Exercise 1 (p. 46) complementing the finite automaton
- Exercise 2 (p. 75) pumping lemma for complement language
- Exercise 3 (p. 79) closure properties of quotient
-
in the exercise section
- Exercise 4 give DFAs for some simple languages
- Exercise 5 give FAs for some harder languages
- Exercise 6 see quickly why some languages are regular
- Exercise 7 describe languages accepted by given DFAs
- Exercise 8 assertions about regular languages
- Exercise 9 give DFAs and NFAs for some languages and bound the DFAs
- Exercise 10 modify an FA to remove epsilon from its language
- Exercise 11 modify a DFA to prevent reentering the start state
- Exercise 12 give an NFA and a DFA for nonassociative expressions
- Exercise 13 prove that every regular language has a planar NFA
- Exercise 14 prove that some regular language have no planar DFA
- Exercise 15 write regular expressions for some languages
- Exercise 16 assertions about regular expressions
- Exercise 17 classify languages as regular or not regular
- Exercise 18 give different proofs of non-regularity for a language
- Exercise 19 regularity of some 2-component vector languages
- Exercise 20 regularity of some 3-component vector languages
- Exercise 21 regularity of Roman numerals
- Exercise 22 regularity of a subset of regular expressions
- Exercise 23 regularity of nonassociative arithmetic
- Exercise 24 characterization of unitary languages
- Exercise 25 closure properties of regular languages
- Exercise 26 subsequences of a regular language
- Exercise 27 circular permutations of a regular language
- Exercise 28 prefix-free subset of a regular language
- Exercise 29 first half of palindromes in a regular language
- Exercise 30 first and last third of strings in a regular language
- Exercise 31 th out of pieces in a regular language
- Exercise 32 complex subpieces of a regular language
- Exercise 33 subsequences of any language
Additional Exercises