首页 > > 详细

代做Comp 330 (Fall 2024): Assignment 3代做留学生SQL 程序

项目预算:   开发周期:  发布时间:   要求地区:

Comp 330 (Fall 2024): Assignment 3

1.  (20 points)  Let Gbe a context-free grammar (CFG) in a Chomsky Normal Form (CNF).

S  → AB

A  → BB | a

B  → AB | b

Use the Cocke-Younger-Kasami (CYK) algorithm to decide if the string s = aabbb is a word of the language L(G). If yes, draw a derivation tree for s computed from your execution of the CYK algorithm. Highlight the symbols selected in the CYK tables.

2.  (10 points)  Using the pumping lemma for regular languages, show that the language L of words over the alphabet Σ = {a} whose length is a prime number is not a regular language.

3.  (10 points)  Describe a Turing machine that computer and writen + 1 for a input number n written binary notation on the input tape.  Here, we assume that the binary number is written from left to right from the least significant bits to the most significant bits.

4.  (30 points)  Consider the following language

L = {w#w : w ∈ {a, b}*}

Show that this language is decidable by

1.  Providing a high-level description of a deterministic infinite tape Turing machine M which decides it.

2.  Providing the state transition diagram of M.

You do not need to prove the correctness of your construction.

5.  (30 points)  Let Σ = {0} and consider the following function f : Σ+  → Σ+ f (x) = x · x · x. Show that fis a total computable function by

1.  Providing a high-level description of a deterministic infinite tape Turing machine M which computes f.

2.  Providing the state transition diagram of M.

You do not need to prove the correctness of your construction.





软件开发、广告设计客服
  • QQ:99515681
  • 邮箱:99515681@qq.com
  • 工作时间:8:00-23:00
  • 微信:codinghelp
热点标签

联系我们 - QQ: 9951568
© 2021 www.rj363.com
软件定制开发网!