TOC

The branch of computer science that deals with how efficiently

the problem can be solved on a model of computation, using an
algorithm.
Branches:
· Automata theory and language
· computability theory
· complexity theory
Automata theory and language:
It deals with definition and properties of various mathematical
model of computation like finite automata,context free
grammer, turing machine.
Computibility theory:
It deals with what can and cannot be computed by the model.
Complexity theory:
It group the computible problems based on hardness.
Main purpose of theory of computation:
· Develop a formal mathematical model of computation that reflect
real world computers.

Definitions:
Symbol: It is a character. e.g, a,b,c,1,2,3,+,- etc.

Alphabet:Finite and non empty set of characters.

= {a,b,c..x,y,z} or {0,1} or {+,-,%,#}

String: A finite set sequence of symbols choosen from some alphabet.

e.g, 011101010 in {0,1} , aabbdd in {a,b,d}

Empty String: The string with zero occurance of symbols. It is denoted by 'E'.

Length of string: no. of symbols in the string.It denoted by |w|.

Concatination of string: join two or more strings.

Power of alphabet: Set of strings over an alphabet having sigma power

k entries.

sigma closure = sigma^0 U sigma^1 U sigma ^2 ......

kleen plus = sigma^ + = sigma closure - sigma^0

Language : fininte set of non empty string

If sigma is an alphabet and L is subset of sigma closure then L is a

language.

· L complement = sigma closure - L

· Concatination = L1.L2 = {w1.w2| w1 is in L1 and w2 is in L2;

· Reversal = Lr ,{wr,w is in L}

· Kleen closure = L* = i=0Uinf(Li)

· Positive Closure = L+ = i=1Uinf(Li)

Finite automata: Finite automata is an abstract computing device. It is
a mathematical model of a system with discreate inputs, outputs, states
and set of transitions from state to state that occurs on input symbols
from alphabet.

It can be represented by:

· Graphical - transition diagrams

· Tabular - Transition table

· Mathematical - Transition function or mapping function

Formal definition:
A finite automata is a five tuple which are

Q : it is finite set called the states.

sigma: is a finite set called the alphabets.

delta : is the transition function.

q0 : initial state

F: Final state

Transition diagram:
It is a directed graph associated with the vertices of the graph corresponds to the
state of finite automata.
Transition table:
It is tabular representation of the transition function that takes two
arguments (a state and a symbol) and returns a value(the next state).

rows - states

columns - input symbols

entries - next state

start state is marked with arrow

final state is marked with star(*)

Transition function or mapping function:

It takes current state and input symbol gives next state.

Applications:

· compiler design

· switching theory and design, analysis of digital circuits

· design and analysis of complex software and hardware

· To design finite state machine like moore and melay

· it is base for formal languages

Deterministic Finite Automata(DFA):

 · The FA is said to be deterministic if the machine on input string read one
symbol at a time.

· Deterministic refers to the uniqueness of the computation.

· In DFA, there is only one path for specific input from the current state to the
next state.

· DFA does not accept the null move, i.e, DFA cannot change state withour
any input characters.

· DFA can contain multiple final states. It is used in lexical analysis in compiler.

Acceptance of language:

A language is accepted if a string w is accepted by the machine M i.e, if

it is reaching the final state F by taking the string W.

Not accpeted if it doesnot reach the final state.

no. of states = min string +1

Non Deterministic Finite Automata(NDFA):

· The FA are called NFA, when there exist many paths for specific i/p
from the current state to the next state.

· It is easy to construct NFA than DFA for a given regular language.

· Every NFA is not DFA, but each NFA can be translaed into DFA.

· NFA is defined in the same way as DFA, but with two exceptions,

1. It contains multiple next state.

2. it contains epsilon transitions in epsilon NFA.

Transition function:
next state posiblity is power set.

means there may be 2Q no. of states.

· Graphical representation is same as DFA.

NFA with empty Symbol( ):

here transition function is

means there are epsilon moves unlike DFA and NFA.

Acceptance by NFA:

A string 'w' is said to be accepted by NFA if there exist at least one

transition path on which we start at initial state and ends at final state.

Conversion of NFA to DFA:

while converting, multiple states are considered as one state and there
can be atleast 1 and atmost 2m states in DFA.

Regular language:

If a language is accepted by finite automata or derived from a Regular

Grammer or represented by regular expressions.

A language is regular if

· the language is finite

· empty
 · infinite but remembering the order and no comparison and no
counting.

REGULAR EXPRESSION:

· A way of representing RL

· expression of strings and operators.

like a* , a+,a.b(concat),a+b(union)

primitive and non premitive Regular Expression:

· RE is said to be valid iff it can be derived from primitive RE by a

finite number of application of the rules r*,r+,r1+r2,r1.r2

· if sigma is a given alphabet then, empty(fii) , epsilon or lambda ,

symbol belongs to sigma are primitive regular expression.

Grammer
Grammer is defined by a quadruple

G = { sigma,Vn, P, S}

sigma = finite set of terminals or small case.

Vn = finite non-empty set of non terminals or upper case.

P = finite non-empty set of production rules.

S = start symbol

Chomsky hierarchy:

· Type 0 grammer or Recursive enumerable grammer or

 Unrestricted grammer or phase structured grammer:

It is used to genrate Recursive enumerable language(REL) which is

accepted by turing machine (TM).

· Type 1 grammer or length increasing grammer or non contracting

grammer:

It genrates context sensitive language which is accepted by linear

bounded automata (LBA).

PDA(Push down Automata):

PDA = {Q, sigma, q0, F, z0, stack aplhabet, delta}

Q = finite set of states.

sigma = input alphabet.

q0 = initial state .

F = set of final states.

z0 = bottom/initial stack of symbol.

delta = transition function.

Turing Machine:

It is a mathematical model of computation that defines abstract

computer . 1936 Alan turing

T.M = {sigma, Q, q0, F, tau, B, delta}

sigma = input symbol,

Q = set of states.
q0 = intitial state

F = set of final state

tau = tape alphabet.

B = blank symbol

delta = Q * sigma----> Q *tau*(L/R).