CS701 - Assignments

Newer 12 11 10 9 8 7 6 5 4 3  2  1 Older

CS701 – Theory of Computation

Due Date: 21^st Nov, 2012

Assignment 1

Instructions to Solve Assignments

The purpose of assignments is to give you hands on practice. It is expected that students will solve the assignments themselves. Following rules will apply during the evaluation of assignment.

·         Cheating from any source will result in zero marks in the assignment.

·         Any student found cheating in any two of the assignments submitted will be awarded "F" grade in the course.

·         No assignment after due date will be accepted.

Question 1: Total Points (10)

Following is the Turing Machine M₁ for the language 

For each of the following input strings, provide the sequence of configurations that M₁ enters.

(a) 0000

(b)00000

(c) 000000

(d)0000000

(e) 00000000

A) Sequence of configurations of M₁ for 0000

q₁0000

□q₂000

□xq₃00

□x 0q₄0

□x0xq₃□

□x0q₅x□

□xq₅0x□

□q₅x0x□

q₅□x0x□

□q₂x0x□

□xq₂0x□

□ xxq₃x□

□ xxxq₃□

□ xxq₅x□

□ xq₅xx□

□ q₅xxx□

q₅□xxx□

□ q₂xxx□

□ xq₂xx□

□ xxq₂x□

□ xxxq₂□

□xxx□q_accept

B) Sequence of configurations of M₁ for 00000

q₁00000

□q₂0000

□xq₃000

□x 0q₄00

□x0xq₃0

□x0x0q₄□

□x0x0□q_reject

C) Sequence of configurations of M₁ for 000000

q₁000000

□q₂00000

□xq₃0000

□x 0q₄000

□x0xq₃00

□x0x0q₄0

□x0x0x q₃□

□x0x0q₅x□

□x0x q₅0x□

□x0 q₅x0x□

□x q₅0x0x□

□q₅x0x0x□

q₅□x0x0x□

□q₂x0x0x□

□xq₂0x0x □

□xxq₃x0x □

□xxxq₃0x□

□xxx0q₄x□

□xxx0xq₄□

□xxx0x□q_reject

D) Sequence of configurations of M₁ for 0000000

q₁0000000

□q₂000000

□xq₃00000

□x 0q₄0000

□x0xq₃000

□x0x0q₄00

□x0x0xq₃0

□x0x0x0q₄□

□x0x0x0□q_reject

E) Sequence of configurations of M₁ for 00000000

q₁00000000

□q₂0000000

□xq₃000000

□x 0q₄00000

□x0xq₃0000

□x0x0q₄000

□x0x0xq₃00

□x0x0x0q₄0

□x0x0x0xq₃□

□x0x0x0q₅x□

□x0x0x q₅0x□

□x0x0q₅x0x□

□x0xq₅0x0x□

□x0q₅x0x0x□

□xq₅0x0x0x□

□q₅x0x0x0x□

q₅□x0x0x0x□

□q₂x0x0x0x□

□xq₂0x0x0x□

□xxq₃x0x0x□

□xxxq₃0x0x□

□xxx0q₄x0x□

□xxx0xq₄0x□

□xxx0xxq₃x□

□xxx0xxxq₃□

□xxx0xxq₅x□

□xxx0xq₅xx□

□xxx0q₅xxx□

□xxxq₅0xxx□

□xxq₅x0xxx□

□xq₅xx0xxx□

□q₅xxx0xxx□

q₅□xxx0xxx□

□q₂xxx0xxx□

□xq₂xx0xxx□

□xxq₂x0xxx□

□xxxq₂0xxx□

□xxxxq₃xxx□

□xxxxxq₃xx□

□xxxxxxq₃x□

□xxxxxxxq₃□

□xxxxxxq₅x□

□xxxxxq₅xx□

□xxxxq₅xxx□

□xxxq₅xxxx□

□xxq₅xxxxx□

□xq₅xxxxxx□

□q₅xxxxxxx□

q₅□xxxxxxx□

□q₂xxxxxxx□

□xq₂xxxxxx□

□xxq₂xxxxx□

□xxxq₂xxxx□

□xxxxq₂xxx□

□xxxxxq₂xx□

□xxxxxxq₂x□

□xxxxxxxq₂□

□xxxxxxx□q_accept

=================================================================

Question 2: Total Points (10)

Suppose for a programming language, a valid variable name has the following properties:

• Only Alphabets (a, b, c, ... , z, A, B, C, ... , Z) and Numerals (0, 1, 2, ... , 9) are allowed in variable name.
• Variable name can only start with Alphabets.
• Maximum length of variable name is 8.
• The keywords defined for the language cannot be a variable name.

Let L be the set of all such valid variable names.

(a)  Prove that L is finite.

(b) How many strings does L contain (excluding the keywords condition stated above)?

§  Answer for Question No. 2

• B)
• The maximum length of variable is 8 it means the language has all variables of length 1, 2, and so on up to length 8.
• Because only alphabets are allowed at first position, so there are 52 choices for the first position. For other seven positions there are 62 choices.
•  
• Therefore total numbers of strings of L are:
• 52 + 52(62)¹ + 52(62)² + 52(62)³ + 52(62)⁴ + 52(62)⁵ + 52(62)⁶ + 52(62)⁷
• = 
  
• = 186125991646140 strings
•  
• •  
  • A) The language L is finite if and only if it has finite many strings. We have calculated the number of strings (excluding the keyword condition) to be 186125991646140
  • Including the keyword condition the total number of strings will be less than the above counting number which is a surely a finite number.
  • So our language L is Finite.
  •  
  • =================================================================
  
  
  
  
  Question 3: Total Points (40)
  For each of the following languages, provide implementation-level and Formal description of Turing Machines.
  (a)             A = { 0ⁿ1ⁿ2ⁿ | n ≥ 0 }
  (b)            B = { 0ⁱ10^j | 0 ≤ i < j }
  
  
                
  [Note: Formal description also includes transition diagram.]
  
  
  Answer for Question No. 3
  
  
  A)        A = { 0ⁿ1ⁿ2ⁿ | n ≥ 0 }
  Implementation-Level Description:
  1.    On input string x
  2.    If the string is empty then accept else continue.
  3.    Check that the format of the string is of the form 0*1*2*. If no then reject and if yes then continue
  4.     Cross the first ‘0’ and first ‘1’ and first ‘2’ in the string.
  5.    Come back to the start of the string and then again move forward and cross next ‘0’ and cross next ‘1’ and next ‘2’.
  6.    Repeat the step 5 unless either all 0’s or all 1’s or all 2’s are crossed.
  7.    If we find all 0’s, 1’s, and 2’s crossed, then accept; else reject.
    
  Formal Description:
  ·         Q= {q₀, q₁, q₂, q₃, q₄,q_accept}
  ·         ∑= {0, 1, 2}
  ·         Г = {0, 1, 2, □, x}
  ·         q₀ is the start state, q_accept is the accept state and q_reject is the reject state.
  ·         ∂ (gamma) is the transition function given by the following transition diagram.
  Note that in the below diagram, every transition that is not mentioned goes to the reject state
  
  
  
  

B)        B = { 0ⁱ10^j | 0≤ i < j }

Implementation-Level Description:

1.    On input string x

2.    Check that the format of the string is of the form 0*10*. If no then reject and if yes then continue

3.    Cross the first ‘0’ in the string, move forward to find ‘1’ in the string, when ‘1’ found then cross the next ‘0’ that comes after ‘1’

4.    Come back to the start of the string. Go forward and cross the next ‘0’ in the string and then also cross the next ‘0’ after ‘1’

5.    Repeat step 4 unless all the 0’s to the right side of ‘1’ or to the left side of ‘1’ are crossed.

6.    If there are one or more 0’s remaining to the right side of ‘1’ accept. If no ‘0’ on either side of ‘1’, reject. If one or more 0’s remaining to the left side of ‘1’, reject

 

Formal Description:

·         Q= {q₀, q₁, q₂, q₃, q₄, q₅,q_accept}

·         ∑= {0, 1}

·         Г = {0, 1, □, x}

·         q₀ is the start state, q_accept is the accept state and q_reject is the reject state.

·         ∂ (gamma) is the transition function given by the following transition diagram.

Note that in the below diagram, every transition that is not mentioned goes to the reject state

=================================================================

Question 4: Total Points (10)

For this question, consider ∑ = { 0, 1 } and ɼ = { 0, 1, ˽ }

(symbol ˽  means blank)

Describe the language accepted by each of the following Turing Machines.

(a)  M₁ with transition function as:

δ(q₀, 0) = (q₁, 1, R)

δ(q₁, 1) = (q₀, 0, R)

δ(q₁, ˽) = (q_a, ˽, R)

(b) M₂ with transition function as:

δ(q₀, 0) = (q₀, ˽, R)

δ(q₀, 1) = (q₁, ˽, R)

δ(q₁, 1) = (q₁, ˽, R)

δ(q₁, ˽) = (q_a, ˽, R)

(c)  M₃ with transition function as:

δ(q₀, 0) = (q₁, 1, R)

δ(q₁, 1) = (q₂, 0, L)

δ(q₂, 1) = (q₀, 1, R)

δ(q₁, ˽) = (q_a, ˽, R)

[Note: Describe languages as provided in the statement of question 3.]

Answer for Question No. 4

A)   L(M₁) = { (01)ⁿ0   |  n≥0 }

B)   L(M₂) = { 0ⁿ1^m    |   n≥0, m≥1 }

C)   L(M₃) = { 0(110)ⁿ | n≥0 }

=================================================================

Question 5: Total Points (20)

Read the paper titled “Turing Machines with Two Letters and Two States”, and explain how it is possible to decide halting problem for this two letters and two states Turing machine.

Question 6: Total Points (10)

Read the paper titled “Penguins And Pandas: A Note On Teaching Cantor’s Diagonal Argument”, and justify how non-numerical variations of Cantor's diagonal argument is easy to understand as compared to the original argument.

Answer for Question No. 6

Yes it is true that the non-numerical variation of Cantor’s diagonal argument is easier to understand as compared to the original argument.

On one hand, by reading this paper, we easily understand the power of Cantor’s diagonal argument, while one the other hand, we also easily understand the uncountable infinite sequences of infinite elements, even if we don’t have much knowledge of number theories in mathematics.

Creating Cantor’s special sequence by using the images of penguin and pandas is easier than creating it using real numbers; because thinking about two images i.e. penguin and panda is easier than thinking of real numbers(with decimal point and 0 to 9 digits).

Contradicting element and its contradiction can also be understood more easily when there are two images penguin and panda instead real numbers.

Writer has observed that the students become quite creative in constructing contexts for proving that certain sets are uncountable when they are not limited to sets of numbers. The animal sequences and songs offer a familiar vehicle for leading fine arts and humanity students to an appreciation of uncountable sets and levels of infinity.

Download: Click here