Theory of Computation: alphabet and languages

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.

Alphabets

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

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

Strings or words over Σ

Consider alphabet , Σ = { 0,1 }

w₃= 010 , w4= 0111

Suppose 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₃= 010 , w₄= 0111

w₇= 0100111 is concatenation of w_{3 .} w_{4 .}

w₁ w₂ = ε . b = b . ε = b , where w₁= ε and w₂= b