What is this subject called Theory of Computation?

It is one of most important topic of computer science. It involves heavy use of mathematics.

What is taught in the subject ?

computer uses algorithms than receive input and produce precise output. The algorithm themselves are nothing but mathematical functions. These functions receives inputs and gives outputs consistently.

but certain class of mathematical functions does not have any algorithms, or algorithms that does not work on all inputs.

There is graph associated with every function and this graph of f consists of a pair

graph(f(x))=(x,f(x) ).

If a function has this set or tuple, then that function admit algorithms that solve problems for given input.

Theory of Computation is to find whether a given input belongs to this set, this problem is known as the set membership problem.

We try to solve this set membership problems for given strings or languages.

## Fundamental concepts

### Symbols

Any single object is called symbol.

for example:-

1,0, A , a , @ , # are symbols.

for example:-

1,0, A , a , @ , # are symbols.

### Alphabets

Alphabet is finite, non-empty set of symbols denoted by Σ.

Σ = { 0,1 } , Σ = {a,b,c} are examples of alphabet.

Σ = { 0,1 } , Σ = {a,b,c} are examples of alphabet.

### Strings or words over Σ

Consider alphabet , Σ = { 0,1 }

w

Suppose the alphabet is Σ = { a, ε}

w = a ε = ε a = a , where ε is an empty string.

w

_{3}= 010 , w4= 0111Suppose the alphabet is Σ = { a, ε}

w = a ε = ε a = a , where ε is an empty string.

### length of string

It is the number of symbols in the string w. The length of empty string is 0.

|ε | = 0

| w| = | a a b a| = 4 ,

It does not matter if the alphabets are repeated.

### Concatenation of strings

It is nothing but to join two shorter strings to make a single larger string.

w

_{3}= 010 , w_{4}= 0111

w_{7 }**= 0100111 **is concatenation of w_{3 . } w_{4 .}

w_{1} w_{2} = ε . b = b . ε = b , where w_{1 }= ε and w_{2 }= b

Advertisements