CS181 Machine Learning Homework- Harvard University
I. Construct one-tape, deterministic Turing machines that decide the languages below. You must provide both a state-transition diagram and a detailed verbal description:
i. binary strings of the form (0n1)k, where n ≥ 0 and k ≥ 0;
ii. binary strings (including ε) that represent properly nested parentheses, where 0 denotes an open parenthesis and 1 denotes a close parenthesis.
II. Give an algorithm that takes as input a DFA D and determines whether D accepts at least two palindromes.
III. A language L is called downward-closed if for every string w that L contains, L also contains every prefix of w. Give an algorithm that takes as input a regular expression R and decides whether the language that R generates is downward-closed.
IV. A variable T in a context-free grammar C is called essential if every derivation of every string by C uses the variable T. Give an algorithm that takes as input a context-free grammar C and a variable T, and decides whether T is essential in C.
V. A string w is said to cover a given PDA P if there is a computation by P on w suchthat every state of P is visited. Give an algorithm that takes as input a PDA P and decides whether there is a string that covers P.
VI. Prove that every infinite decidable language can be partitioned into two disjoint infinite decidable languages.
VII. For each problem below, determine whether it is decidable and prove your answer:
i. on input a Turing machine M and a symbol σ, decide whether M ever writes σ on the tape in any computation;
ii. on input a Turing machine M, decide if M recognizes a decidable language.
Format your homework according to the following formatting requirements:
i) The answer should be typed, using Times New Roman font (size 12), double spaced, with one-inch margins on all sides.
ii) The response also includes a cover page containing the title of the homework, the student's name, the course title, and the date. The cover page is not included in the required page length.
iii) Also include a reference page. The Citations and references must follow APA format. The reference page is not included in the required page length.