2023年11月25日

计算性与复杂性代写 | CMSI 583 Midterm Exam

本次美国代写是计算性与复杂性的一些相关习题

1. Let L1 be the set of binary strings such that any 1’s are proceeded by one or two 0’s.

(a) [10 points] Give a regular expression for L1.
(b) [10 points] Draw a finite automata that accepts L1

2. Consider the language L2 that is the set of all binary strings that contain a number of 1’s that is even
and greater than zero.

(a) [10 points] Give a context-free grammar for L2.
(b) [5 points] Give a derivation of the string 0110110 in your grammar.
(c) [10 points] Give an informal English description of a pushdown automata that accepts L2.

3. [15 points] Show that the language L3 of all binary strings that have length that is a power of 3 ( i.e.
length equals 3i for some integer i  0) is not regular.

4. [20 points] Give implementation-level pseudo-code for a Turing Machine that decides the language,
L4 containing all binary strings that have length that is a multiple of 7. (You need only explain how
the tape will be used in the algorithm and do not have to give all states of the finite control or the
transition function.) Trace your implementation on one string that would be accepted and another
string that would be rejected by your Turing machine.

5. [10 points] Let L5 = f< R1;R2 > j R1 and R2 are regular expressions and L(R1) = L(R2)g. L5 is a
language containing all strings that contain pairs of regular expressions that accept the same language.
Show that L5 is decidable.

6. [10 points] Let L6 = f< M > j Turing Machine M accepts all binary strings g. Recall that ATM,
HALTTM, and EMPTYTM are all undecidable. Use any of these languages to show that L6 is unde-
cidable. (Please do not use Rice’s Theorem.)