CS 21 Decidability and Tractability Winter 2024
Out: January 10
Due: January 17
Problem Set 1
Copyright By PowCoder代写 加微信 powcoder
Reminder: you are encouraged to work in groups of two or three; however you must turn in your own write-up and note with whom you worked. You may consult the course notes and the text (Sipser). The full honor code guidelines and collaboration policy can be found in the course syllabus.
Please attempt all problems. Please turn in your solutions via Gradescope, by 1pm on the due date.
1. Let f : Σ∗ → Σ∗ be an arbitrary function. You are asked to (1) define a related language Lf ⊆ Γ∗, and (2) describe how a computer program could use a procedure that decides Lf to compute f, and vice-versa. Here Γ is an alphabet that may or may not be the same as Σ. Ideally, on input x, your program should invoke the procedure that decides Lf at most polynomially many times in the length of x and the length of f(x), (but attaining this quantitative goal is not required to get full credit for this problem).
This justifies our use of languages (or decision problems) rather than the more general notion of function problems.
2. This problem is based on Problem 1.38 (Problem 1.31 in the First Edition), which defines a new kind of automaton: the all-paths-NFA. An all-paths-NFA is defined by a 5-tuple (Q, Σ, δ, q0, F ) just like an NFA. The only difference is in the acceptance criterion. An all-paths-NFA accepts a string x if every computation of M on x ends in an accept state (computations that “die” before reading to the end of the input are not counted). For com- parison, recall that an NFA accepts a string x if some computation of M on x ends in an accept state.
(a) Prove that L is a regular language if and only if L is recognized by an all-paths-NFA.
(b) Use part (a) to prove that the regular languages are closed under intersection. That is,
prove that if A and B are regular languages, then
C = (A ∩ B) = {x : x ∈ A and x ∈ B}
is a regular language.
(c) LetM=(Q,Σ,δ,q0,F)beanNFAthatrecognizeslanguageL.LetMflip=(Q,Σ,δ,q0,F′) be the all-paths-NFA defined by taking F ′ = Q − F , and let Lflip be the language rec- ognized by Mflip. How are L and Lflip related? Briefly justify your answer.
3. A palindrome is a string that reads the same forwards as backwards (ignoring spaces); an example is “lonely tylenol”. Let Σ be the 26 letter English alphabet. Prove that the language consisting of all palindromes is not regular.
4. A language over an alphabet Σ with only one symbol is still meaningful. It is called a unary language. In this problem Σ = {0}.
(a) For a positive integer n, define the language Ln ⊆ Σ∗ to be the set of all strings whose length is not divisible by n. Prove that for all n ≥ 1, Ln is a regular language.
(b) Prove that the language primes ⊆ Σ∗, consisting of all strings whose length is a prime number, is not regular.
Spend a few minutes to convince yourself that this does not contradict Problem ??(b), in which you proved that the regular languages are closed under intersection. You do not need to write down and turn in your thoughts (but you can if you wish).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com