Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CompSci 162 Formal Languages and Automata Problem Set 1
Formatting: please start each numbered question on a separate piece of paper, and limit your response to one page. If you wish to do 1(a) and 1(b), and/or 3(a) and (b), on separate pages, you may do so. Upload a PDF consisting of these three to five pages to GradeScope and tag each page. Write in dark ink on light paper, whether you are producing your work digitally or on physical paper. I realize this seems strict, but it really does help with grading, especially with a large class.
Please review the syllabus and course reference for the expectations of assignments in this class. Remember that problem sets are not online treasure hunts. Remember that you may not seek help from any source where not all respondents are subject to UC Irvine’s academic honesty policy.
Please also remember you have a professor and four TAs who want to help you. If you’re lost on this, let us know!
1. If you would prefer to put (a) and (b) on separate pieces of paper, you may; just be sure to tag them correctly when you upload.
(a) Prove that |N| = |N×N| by giving an explicit bijective function. Your submission should include both the function and an explanation of how you derived it; that explanation should also allow the reader to understand why the function is bijective.
(b) Prove that |N| = |N × N| by using the Schr¨oder-Bernstein Theorem. Give a sentence explaining the category for each function and a brief description
2. Construct a DFA that recognizes strings in {0, 1} ∗ with the following property. Each string, when interpreted as a binary number, is congruent to 3 modulo 5. That is, the remainder is 3 when divided by 5. Give both a state diagram and a formal description of the machine (define what Σ is, Q, q0, etc). Note that the binary number is input in the natural left-to-right manner; that is, with the most significant digits appearing first on the tape. Give a sentence or two description of why your machine is correct.
3. For each of the following languages over the alphabet Σ = {a, b, c}, use mechanisms from lecture to either show it is regular or prove that it is not. If you would prefer to put (a) and (b) on separate pieces of paper, you may; just be sure to tag them correctly when you upload.
(a) L1 = {w ∈ Σ ∗ | |w| is a power of 2}
(b) L2 = {w ∈ Σ ∗ | |w| is a multiple of 3}.