Hamid Raza - CS-73

Course Code : CS-73
Course Title : Theory of Computer Science
Assignment Number : BCA(6)-73/Assignment/2009
Maximum Marks : 25
Last date of Submission : 30th April, 2009/30th October, 2009

This assignment is having five questions. Answer all the questions.

Q.1
Define the following concepts formally/mathematically, with one example for each:

a) Regular Language
Language represented by a regular expression is called a regular language. In other words, we can say that a regular language is a language that can be represented by a regular expression.
For a given alphabet ∑, the following fules define the regular language associated with regular expression.

Rule 1 : ф, {^} and {a} are regular languages denoted respectly by regular expression ф and ^.
Rule 2 : For each a in ∑ , the set {a} is a regular language denoted by the regular expression a.
Rule 3 : If l is a regualr expression associated with the language L and m is a regualr expression associated with the language m, then :

(i) The language = {xy : x Є L and y Є M} is a regualr expression associated with the regualr expression lm.
(ii) The regualr expression l+m is associated with the language formed by the union of the sets L and M.
(iii) The language associated with the regualr expression (l)* is (L)*, the Kleen Closure of the set L as a set of words :
language (l)* = L*.

Example :

If L={aa,ab,ba,bb}, then the corresponding regular expression is aa+ab+ba+bb.
Another regular expression that defines this language is (a+b)(a+b)

b) Primitive Recursive Function
    The functions, obtained by applying a finite sequence of the structuring rules to the initial functions, are called primitive Recursive functions.
      The set of primitive recusive functions is obtained by three types of initial functions (which are lementary primitive functions) and three structuring rules for constructing more complex functions from alteady constructed functions.
      Three types of initial functions :

(i) The 0-Place zero function ξ from N⁰to N such ξ()=0

(ii) The successor function
          σ : N -> N
          such that
          σ(n) = n+1         for all n Є N
(iii) The projections : we know that for K > 1, N^kis the set of all k-tuples of the form ñ = (n¹, n², ......nⁱ, nⁿ) for 1 < i < k.
For each fixed i, with 1 < i < k, we may define a function, denoted by ∏^k_i, with
∏^k_i : N^k -> N such that for ñ = (n¹, n², ......nⁱ, nⁿ)
∏^k_i ñ = ∏^k_i(n¹, n², ......nⁱ, nⁿ) = n_i

Thus, we have defined k projection functions, each with domain N^k, viz.
∏^k_1,∏^k_{2, ...,}∏^k_i,...∏^k_kand each of which maps to N. for the sake of explanation, we have ∏⁵₃(e, -7, 12, 4, 3) = 12.
Finally, the zero-place zero function ξ, the successor function σ and the projection function ∏^ki for K Є N, and i Є N, with 1 < i < k, are the only initial functions, which are also called elementary primitive functions.

The three structuring rules are.
(i) Combination.
(ii) Composition and
(iii) Primitive recursion.

(i) Combination as a Structuring rule

The combination of two funtion
g : N^k -> N
h : N^k -> N
is a function
f : N^k -> N x N

Such that for ( n_{i ,.....,}n_k) = ñ Є N^k,
f(ñ) = (g(ñ), h(ñ)).
Then, the function f is denoted by gxh and is called combination of g and h.

(ii) Composition as a structuring Rule

Let g : N^k -> N^p and
h : N^p -> N^q for k,p,q Є N
be two given functions.
Then we define a function
f : N^k -> N^p
as follows :
if (n_{1 ,}n_{2 ,}_.....,n_k) Є N^k and
g (n_{1 ,}n_{2 ,}_.....,n_k) = (m_{1 ,}m_{2 ,}_.....,m_p) Є N^p

further, if
h (m_{1 ,}m_{2 ,}_.....,m_p) = (t_{1 ,}t_{2 ,}_.....,t_p) Є N^p

then
f : is such that
f
= h(g(n_{1 ,}n_{2 ,}_.....,n_k))

= h (m_{1 ,}m_{2 ,}_.....,m_p) = (t_{1 ,}t_{2 ,}_.....,t_p)

      The function f, so defined, is called the compostion of g and h and is deonoted by n.g.

(iii) Primitive Recursion
        Using primitive recursion a function can be define recursively through
          f(x,0) = g₁(x)
          f(x,y+1) = h(g₂(x,y),f(x,y)),
      from defined functions g₁,g₂, & h.

Example :
        Addition of integers x and y can be implemented with the function add(x,y) defined by
             add(x,0) = x
             add(x,y+1) = add(x,y)+1

      To add 2 and 3, we apply these rueles successily.
             add(3,2) = add(3.1)+1
                          = add((3,0)+1)+1
                          = (3+1) + 1
                          = 4+1 = 5

c) Turing Machine

d) Unsolvable Problem

e) Turing-Decidable Problem

    A broblem is daid to be turing-decidable if there exists a truring machine that gives the correct answer for every statement in the daomain of the problem.
    A problem P is said to be Decidable if the language L C ε* representing the problem is Turing decidable. A language L C ε* representing a problem over ε, is said to be turing Decidable, if there is a Turing Machine M which always halts when given the input   w Є ε*   whether   w Є L then M halts with output Y, indicating that the string w is in the language L, and if w Є L the M halts with output N. indication that string w doesn't belngs to L.

f) Mealy Automata

g) Universal Turing Machine

h) Deterministic Finite Automata
      A DFA represents a finite state machine that recognizes a RE.
      A DFA accepts a string if starting from the start state and moving from state to state, each time following the arrow that corresponds the current input character, it reaches a final state when the entire input string is consumed. Otherwise, it rejects the string.
Example.

recognizes (abc⁺)⁺.

i) Context-Free Grammar

j) Godel Number

Q.2
Construct a DFA (Deterministic Finite Automata) accepting the following set :

{w Є {a,b}* : w has an even number of a’s and odd number of b’s}

Ans.

http://www.ziddu.com/download/4505638/Q2._CS-73.doc.html

Download it, it's little difficult to type here.

Q. 3 Construct Turing Machine for the following languages:

(i) {anbncn : n > 1}
(ii) {wwR : w is any string of 0’s and 1’s}

Ans :

http://www.ziddu.com/download/4515789/123.doc.html