[SOLVED] 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.