Cs test now, due in 1and half hours

CS 181 FINAL EXAM WINTER 2020

You have 3 hours to complete this exam. You may state without proof any fact taught in class or assigned as homework. Your algorithms must terminate on all inputs.

1 Construct one-tape, deterministic Turing machines that decide the languages below. You must provide both a state-transition diagram and a detailed verbal description:

a. binary strings of the form (0n1)k, where n ≥ 0 and k ≥ 0;(3 pts) b. binary strings (including ε) that represent properly nested parentheses, where 0(3 pts)

denotes an open parenthesis and 1 denotes a close parenthesis.

2 Give an algorithm that takes as input a DFA D and determines whether D accepts at(3 pts) least two palindromes.

3 A language L is called downward-closed if for every string w that L contains, L also(3 pts) 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.

4 A variable T in a context-free grammar G is called essential if every derivation of every(3 pts) string by G uses the variable T . Give an algorithm that takes as input a context-free grammar G and a variable T, and decides whether T is essential in G.

5 A string w is said to cover a given PDA P if there is a computation by P on w such(3 pts) that 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.

6 Prove that every infinite decidable language can be partitioned into two disjoint infinite(2 pts) decidable languages.

7 For each problem below, determine whether it is decidable and prove your answer:

a. on input a Turing machine M and a symbol σ, decide whether M ever writes σ on(2.5 pts) the tape in any computation;

b. on input a Turing machine M, decide if M recognizes a decidable language.(2.5 pts)