Theory of Automata

Recommended book for Automata click here to download or preview the book
Notes written by Fazal ahad typed by Imdadullah Theory of Automata

1-5/9/2015 By: Ahmad hussain 1 -6

Theory of Automata:

this field of research was started by mathematical in 1930's when the are trying to understand the meaning of a computation the main question 

weather all mathematical problems can be solved in systemative way the research that started in those days led to computer

as we know them today they  have three types.

 

Complexity theory:

 it is the difficulty level of program or mathematical problem.  suppose a problem is called "easy" if it is solvable ie sorting a sequence of 

say 1000000 numbers;

if a problem is called "hard" and cannot be solved i.e time table scheduling for all courses at SPS college.

computability: 

in 1930 Turing and Church discovered that some of the fundamental mathematical problem cannot be solved by a computer e.d in arbitrary mathematical statement

true or false, to solve such problem we need formal definition of the  notion of computer algorithm and computation

the theoretical models that proposed in order to understand the solvable and unsolvable problems, led to the development of real computer.

Automata theory:

 Automata theory deals with definitions and properties of different types of  "computation model" example of models are;

finite automata: these are using in text processing compilers and hard ware designing

context free grammar:

 these are use to define programming languages and in artificial intelligence.

Turning Machines: 

These are a simple abstract model of a "real" computer such as your pc at home.

Finite Automata:

a finite automata is a 5 tuple M=(Q,E,&,q,f)

2-Q These elements are called states.

3-E whose symbols are called alphabet.

4-q is is an element of Q  is called start state.

5-& is called transition function.

6-f is a subset of Q the element of f are called accept states.

Q. Construct finite automata "M" from the follwing definition.

M=(Q,E,&,q,f)

Q={q1,q2}

E={0,1}

&=(q1,0)=q1 &(q1,1)=q2

&=(q2,0)=q1 &(q2,1)=q2

Q;

Q={q0,q1,q2,q3}

E={a,b,c}

&=(q0,b)=q1 &(q1,c)=q0

&=(q1,a)=q2 &(q3,a)=q0

&(q3,b)=q2

start state =q3

f=q2,q1

or

        a  b   c

q0       q1  

q1  q2     q0

q2

q3  q2 q2

q=q3

f=[q1,q2]

finite automata alphabets string a language

Q={q0,q1,q2,q3}

E={t,h,e}

&=

q=q0   f={q3}

Alphabets

  an alphabet is a finite nonempty set of symbols alphabet is denoted by E common alphabet include on

E={0,1} the binary alphabet.

e={a,b...z} the set of all lover case

String

a string is a finite sequence of symbol chosen from some alphabets e.g 01101 is a string from the binary alphabets

E={0,1} every word is a string but every strong is noa a word  a string can be empty and is denoted by E(apsolone)

length of string. the length of string is " the number of symbols" in string there are only two symbols 0,1 in the  string 

01101  in this there is a five position for symbols and its length is five e.g

[0,1]={011101}

so its length is six.