CS/ECE 374 A (Spring 2022) Homework 3 (due Feb 10 Thursday at 10am)
Instructions: As in previous homeworks.
Problem 3.1: For each of the following languages in parts (a), (b), and (c), describe an NFA that accepts the language, using as few states as you can. Provide a short explanation of your solution. Below, #0(x) and #1(x) denote the number of 0’s and the number of 1’s in x respectively.
(a) (30 pts) all strings x ∈ {0,1}∗ such that (x ends with 10101 or 11011) and (#0(x) is divisible by 3 or #1(x) is divisible by 3).
Copyright By PowCoder代写 加微信 powcoder
(b) (30 pts) the language defined by the regular expression ((01)∗0+2)(100)∗1∗ ·(1∗ +0∗2∗) over the alphabet {0, 1, 2}.
(c) (10 pts) all strings in {0, 1}∗ that contains the pattern 0?1?0, where “?” denotes “don’t care” (i.e., a single symbol that is either 0 or 1); in other words, the language defined by the regular expression (0 + 1)∗ · 0(0 + 1)1(0 + 1)0 · (0 + 1)∗.
(d) (30 pts) Convert your NFA from part (c) to a DFA by using the subset construction (i.e., power set construction). [Note: don’t include unreachable states; also, several accepting states can be collapsed into one in this DFA.]
Problem 3.2: Given a language L over the alphabet Σ, define
move-back8(L) = {xayz : xyaz ∈ L, x,y,z ∈ Σ∗, a ∈ Σ, |y| ≤ 8}.
Prove that if L is regular, then move-back8(L) is regular.
(For example, if 010010100110011 ∈ L, then 011001010010011 ∈ move-back8(L).)
[Hint: given an NFA (or DFA) for L, construct an NFA for move-back8(L). Give a formal description of your construction. Provide an explanation of how your NFA works, including the meaning of each state. A formal proof of correctness of your NFA is not required.]