ECE 374 B = Spring 2022
9 Homework 1 :
• Groups of up to three people can 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).
T Some important course policies U
• 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.
See the academic integrity policies on the course web site for more details.
• Avoid the Three Deadly Sins! Any homework or exam solution that breaks any of the
following rules will be given an automatic zero, unless the solution is otherwise perfect.
Yes, we really mean it. We’re not trying to be scary or petty (Honest!), but we do want to
break a few common bad habits that seriously impede mastery of the course material.
– 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.
– Never use weak induction.
See the course web site for more information.
If you have any questions about these policies,
please don’t hesitate to ask in class, in office hours, or on Piazza.
ECE 374 B Homework 1 Fall 2021
1. Give the recursive definition of the following languages. For both of these you should
concisely explain why your solution is correct.
(a) A language LA that contains all palindrome strings using some arbitrary alphabet Σ.
(b) A language LB that does not contain either three 0’s or three 1’s in a row. E.g.,
001101 ∈ LB but 10001 is not in LB.
2. For each of the following languages over the alphabet {0,1}, give a regular expression that
describes that language, and briefly argue why your expression is correct.
(a) All strings that end in 1111.
(b) Strings that do not contain the subsequence 0101010.
(c) The language containing all strings that do not contain 111 as a substring.
(d) All strings that end in 01 and contain 000 as a substring.
(e) All strings where every third 0 is surrounded by 1s
(f) All strings where every nonempty maximal substring of 0s is of odd length (Hint:
maximal 6= maximum).
3. A regular expression is said to be top-plus if it is of the form (α1 +α2 + . . .+αn) for some
n ≥ 1, where none of the regular expressions αi contains an occurrence of +. Show by
induction that every regular language is represented by a top-plus regular expression.
Hints:
• A regular expression is composed of one (or more) sub-expressions connected by one
of three operators. This should give you an idea of what to induct on.
• You may assume that for all regular expressions r and s, (r∗s∗)∗ = (r + s)∗
• Youmay assume a distributive law of concatenation over union, so that r(s+1) = rs+r t
for regular expressions r, s, and t. You may use it more generally, for example
(a+ b+ c)(d + e) = ad + ae+ bd + be+ cd + ce for regular expressions a, b, c, d, and
e.
1