CS 332: Theory of Computation Prof. Boston University September 8, 2021
Homework 1 – Due Tuesday, September 14, 2021 at 11:59 PM
Reminder Collaboration is permitted, but you must write the solutions by yourself without as- sistance, and be ready to explain them orally to the course staff if asked. You must also identify your collaborators and write “Collaborators: none” if you worked by yourself. Getting solutions from outside sources such as the Web or students not enrolled in the class is strictly forbidden.
Problems There are 6 required problems and one bonus problem. Problems 1-4 and 6 are to be turned in via Gradescope. Problem 5 will be autograded using AutomataTutor.
Copyright By PowCoder代写 加微信 powcoder
1. For each of the following languages, (i) give a plain English description of the language, and (ii) give two examples of strings in the language and two examples of strings that are in Σ∗ but are outside the language.
(a) L1 ={0x1|x∈{0,1}∗}
(b) L2 ={w∈{a,b}∗ ||w|≥4}∩{xabbay|x,y∈{a,b}∗}
2. For each of the following languages, (i) describe the language using set-builder notation and union/intersection/complement/reverse/concatenation operations (the notation used in Problem 1), and (ii) give two examples of strings in the language and two examples of strings that are in Σ∗ but are outside the language.
(a) L3 = the set of all strings over alphabet {a, b, c} that are palindromes (read the same forwards and backwards) or start with a. (For example, bacab and cabbac are palindromes.)
(b) L4 = the set of all strings over alphabet {1, 2, . . . , 9} whose length is divisible by a, where a is the first symbol of the string.
3. Which of the following statements are true or false, for all alphabets Σ? For each, provide either a proof or a counterexample.
(a) For all strings x,y,z ∈ Σ∗, we have |xR ◦ ε ◦ zy| = |x| + |y| + |z|. (Recall that ◦ denotes concatenation.)
(b) ForalllanguagesL1,L2 ⊆Σ∗,wehave(L1∩L2)R =LR1 ∩LR2.
(c) ForalllanguagesL⊆Σ∗,wehaveL◦L={ww|w∈L}.
(d) ForalllanguagesL1,L2,L3 ⊆Σ∗,wehaveL1◦(L2∪L3)=(L1◦L2)∪(L1◦L3).
4. Consider the following state diagram of a DFA M using alphabet Σ = {A, B}.
(a) What is the start state of M?
(b) What is the set of accept states of M?
(c) Give a formal description of the machine M (i.e., as a 5-tuple).
(d) What sequence of states does the machine go through on input ABBAB?
(e) Does the machine accept the string ABBAA?
(f) Give a simple description of language recognized by M. (Either plain English or set-builder
notation is fine.)
5. This problem will be autograded using AutomataTutor. Visit http://automatatutor.com/ and click on “Sign Up.” Make an account using your name and @bu.edu email address (it is important for recording grades that the information for your account match the information on the course list provided by the university). We’ll provide more specific information about how to register for this course on Piazza.
Give state diagrams of DFAs with as few states as you can recognizing the following languages. You may assume that the alphabet in each case is Σ = {0, 1}.
(a) L1 = {w | w contains the substring 100}. (b) L2 = {w | w is any string except for 1001}.
(c) L3 = {w | every even position of w is 0}.
Give state diagrams of NFAs with as few states as you can recognizing the following languages.
You may assume that the alphabet in each case is Σ = {0, 1}. (d) L4 = {w | w ends with an odd number of 0’s}.
(e) L5 = {w | the length of w is divisible by either 2 or 3}.
6. Draw (and include in the PDF you submit to Gradescope) state diagrams of DFAs with as few states as you can recognizing the following languages. You may assume that the alphabet in each case is Σ = {0, 1}.
(a) L6 = {w | w is a string of the form x1y1x2y2 . . . xnyn for some natural number n such that
if x is the integer with binary representation x1x2 . . . xn and if y is the integer with binary representation y1y2 . . . yn, then x < y}. Both x and y are presented starting with the most significant bit and may have leading 0s.
(b) L7 = {w | w represents a binary number that is divisible by 4}. The number is presented starting from the most significant bit and can have leading 0s.
Bonus Problem
(a) Show that for any natural number n, the language P ADn = {w ∈ {0, 1}∗ | w ends with n copies of 0} is regular.
(b) Give a state diagram of a DFA recognizing the language ADD = {w | w is a string of the form x1y1z1x2y2z2 . . . xnynzn for some n ≥ 0 such that x + y = z as binary numbers}. Here, x, y, z are presented starting from the least significant bit and can have trailing 0’s. The empty string represents the number 0.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com