CS/ECE 374 A (Spring 2022) Homework 1 (due Jan 27 Thursday at 10am)
Instructions: Carefully read http://engr.course.illinois.edu/cs374/sp2022/A/hw_policies. html and http://engr.course.illinois.edu/cs374/sp2022/A/integrity.html.
Groups of up to three people may submit joint solutions. Each problem should be submitted by exactly one person, and the beginning of the homework should clearly state the Gradescope names and email addresses of each group member. In addition, whoever submits the homework must tell Gradescope who their other group members are.
Submit your solutions electronically on the course Gradescope site as PDF files. Submit a separate PDF file for each numbered problem. If you plan to typeset your solutions, please use the LATEX solution template on the course web site. If you must submit scanned handwritten solutions, please use a black pen on blank white paper and a high-quality scanner app (or an actual scanner, not just a phone camera).
Copyright By PowCoder代写 加微信 powcoder
If you are not using your real name and your illinois.edu email address on Gradescope, you will need to fill in the form linked in the course web page.
You may use any source at your disposal—paper, electronic, or human—but you must cite every source that you use, and you must write everything yourself in your own words.
Any homework or exam solution that breaks any of the following rules may be given an automatic zero.
– Always give complete solutions, not just examples.
– Always declare all your variables, in English. In particular, always describe the specific
problem your algorithm is supposed to solve. – Always avoid unnecessarily long answers.
Problem 1.1: Let L ⊆ {0, 1}∗ be the language defined recursively as follows:
The empty string ε is in L.
For any string x in L, the strings 0101x and 1010x are also in L.
For any strings x, y such that xy is in L, the strings x00y and x11y are also in L. (In other words, inserting two consecutive 0’s or two consecutive 1’s anywhere to a string in L yields another string in L.)
The only strings in L are those that can be obtained by the above rules. Define Lee = {x ∈ {0, 1}∗ : x has an even number of 0’s and an even number of 1’s}.
(a) Prove that L ⊆ Lee, by using induction. (You should use strong induction.) (b) Conversely, prove that Lee ⊆ L, by using induction.
Problem 1.2: Let L = {x ∈ {0,1,…,9}∗ : x does not contain 374 as a substring}.
Obviously, the number of strings in {0, 1, . . . , 9}∗ of length n is equal to 10n.
Prove that the number of strings in L of length n is at most 2 · 9.992n, by using induction.
[Hint: consider two cases: x does not start with 3, or starts with 3. In the second case, consider two subcases: the second symbol is not 7, or is 7.]
[We may give bonus points for a proof of an upper bound better than O(9.990n).]
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com