CS/ECE 374 A (Spring 2022) Homework 2 (due Feb 3 Thursday at 10am)
Instructions: As in Homework 1.
Problem 2.1: For each of the following languages, give a regular expression that describes that language, and briefly argue why your expression is correct. Below, #0(x) denotes the number of 0’s in x, and #1(x) denotes the number of 1’s in x.
(a) All strings in {0, 1}∗ of length at least 5 such that the symbols at positions divisible by 5 are all 0’s. For example: the string 10010111100101011 is in the language because the bold symbols are all 0’s.
Copyright By PowCoder代写 加微信 powcoder
(b) All strings x ∈ {0, 1}∗ such that x does not begin with 101 and #0(x) is divisible by 3.
(c) All strings in {0, 1}∗ that do not contain 0111 as a substring.
(d) All strings in {0, 1, 2}∗ that have at least four 0’s and exactly two 1’s.
Problem 2.2: Describe a DFA that accepts each of the following languages. Describe briefly what each state in your DFA means. For (a)–(c), you should draw the complete DFA. For (d), do not attempt to draw your DFA, since the number of states could be huge; instead, give a mathematically precise description of the states Q, the start state s, the accepting states A, and the transition function δ.
(a) (20 pts) All strings in {0,1}∗ of length at least 5 such that the symbols at positions divisible by 5 are all 0’s.
(b) (20 pts) All strings x ∈ {0, 1}∗ such that x does not begin with 101 and #0(x) is divisible by 3.
(c) (20 pts) All strings in {0, 1}∗ that do not contain 011001 as a substring.
(d) (40 pts) All strings x ∈ {0, 1}∗ such that x contains 09 as a substring, or |x| is divisible
by 8, or #0(x) − #1(x) is divisible by 7.