计算性与复杂性代写 | 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.)


程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持淘宝 支付宝 微信支付  paypal等等交易。如果不放心可以用淘宝交易!

E-mail: itcsdx@outlook.com  微信:itcsdx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论