Assigned:
Wed 14 Jan 2004
Due:
Wed 21 Jan 2004
Problem | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | ... |
---|---|---|---|---|---|---|---|---|---|---|
Credit | RC | RC | RC | EC | RC | RC | NA | RC | RC | ... |
where "RC" is "regular credit", "EC" is "extra credit", and "NA" is "not applicable" (not attempted). Failure to do so will result in an arbitrary set of problems being graded for regular credit, no problems being graded for extra credit, and a five percent penalty assessment.
Required: 7 of the following 9 problems
Points: 14 pts per problem
Note: I would strongly suggest that you attempt and solve this problem. The result itself will be useful for many of the problems below, and the ideas needed to prove it are necessary for many of the remaining problems.
Prove that Even3 is a regular language.
Prove that Multiple5 is a regular language.
Hint: There is nothing special about the number 5; I could just as easily ask the same question for Multiple6, Multiple7, etc. Think "mod"...
In other words, HalfPal(A) consists of those strings which are the first halves of all even length palindromes in A.
In other words, FirstHalf(A) consists of the first halves of all even length strings in A.