CS 525 -- Assignment One

Due Tuesday, May 29th @ 5pm in CS Homework Station

Submission Instructions: Please hand in a hard copy of your solutions to all problems, with a suitable cover page with your name, the date, the course, and the number of the assignment. Do each problem on a separate sheet clearly labelled at the top (e.g., "Problem 3"), and staple all pages together in the upper-left-hand corner (do NOT submit solutions separately or update your solutions after handing in your assignment). For any problem statement that asks multiple questions, answer each in a separate paragraph, labelled (a), (b), etc. Submit "pencil and paper" problems into the CS 210 mail slot (not the shelf) in the CS homework station; submit code or files produced by software using Gsubmit as specified on the course home page. A small penalty will be taken for any homework that does not follow these guidelines.

Late Policy: Both parts of the homework (pencil and paper, and electronic submission) are due at 5 pm on Monday; late homeworks will be penalized at the rate of 25% for each weekday late (each day ending at 5pm, weekends not included).

Policy on Academic Honesty: Please see the end of this homework for comments on the University policy for academic honesty that I adhere to.

Problem 1

1. ((a|b)(a|b)*)* a a (a|b)*

2. ((aa)*b(aa)*)|(a(aa)*ba(aa)*)

3. (a|b)*a(a|b)(a|b)(a|b)

4. (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*)*



5. (b|ab)*(a|b*)

Problem 2

Give DFAs accepting the following regular languages, you may use shorthand notations as presented in class. All strings are over the alphabet {a,b} unless otherwise noted. Notation: #(a) = the number of occurrences of a in the string under discussion.

1. All strings which contain the string ab as a substring.
2. All strings which do not contain the string ab as a subsequence.
3. All strings such that (#(a) mod 3) = 0 and (#(b) mod 3) = 1.
4. The language { a^n | n != 4 } (i.e., strings of a's not of length 4). The DFA you create for this problem MUST have no more than six (6) states.
5. All strings such that any occurrence of aa is immediately followed by a b. (For example, aba, aaba, aabaabbbab are in the language, but aaab and aabaa are not).
6. The language of C comments over the alphabet { /, *, a-z, " }: all string of characters from the alphabet beginning with /* and ending with */ without an intervening */ unless it occurs between a pair of quotes.

Problem 3

Write regular expressions (or, if their complexity warrents it, regular definitions) for the following languages. The languages are over the alphabet {a,b} unless otherwise noted. You may use shorthands as presented in class. Notation: |w| = the length (number of symbols in) w.

1. All strings such that #(a) <= 3.
2. All strings of the form uwu, where |u| = 2 and w is any string.
3. All strings containing an even number of a's.
4. All strings w such that (|w| mod 3) = 2, that is, the length of w is a member of the sequence 2, 5, 8, 11, etc.
5. The language of floating-point constants in C++, as (partially) presented in class last week.

Problem 4

Explain the statement on page 25 of your text: "In the case of s+, it can even ........... expanded regular expression."

Policy on Academic Conduct

Whenever you submit a piece of academic work and sign your name to it, you are verifying that this work is the result of your own intellectual efforts; it is Plagiarism to submit work solely under your own name in which:

• You collaborated with another student in solving the homework problems;
• You copied the solution from a book, web site, or the work of another student; or
• You got significant help in solving the problem, but do not acknowledge this in your solution.

In this course, I will not allow you to submit any joint work, although in other courses and in other contexts you may be permitted to do this. In general, you must always provide proper attribution of authorship by naming all persons, books, or resources that provided intellectual content towards the final result. In some cases, you will need to describe the extend of the contribution, particularly when literally copying the words or artistic artifacts of another. To fail to provide proper attribution is plagiarism. Plagiarism demeans the seriousness of what we do in class, and does not allow you as a student to obtain a fair grade for the results you worked hard for.

I will discuss the issue of plagiarism with the grader, and use, when appropriate, automated tools to check submitted programs and files for copying. I don't like to be involved in this, but it is necessary in order to provide a fair environment for your work. In cases of suspected plagiarism, I will discuss the matter with the student(s) involved and, when warrented, submit the case to the Academic Conduct Committee (of which I was chairman for three years). Unfortunately, students in my classes violate these policies several times a year on average; it is my hope that by being completely clear and straight-forward about my policy that I can reduce this number. Please take this issue serious and talk to me if you have any concerns or questions.