This course presents a study of Finite State Machines and their languages. It covers the details of finite state automata, regular expressions, context free grammars. More, the course includes design of the Push-down automata and Turing Machines. The course also includes basics of undecidabilty and intractability.

To see the syllabus click the link below

**Syllabus **

Notes :

Chapter
1 : PRELIMINARIES

Chapter
2 : FINITE STATE AUTOMATA

Chapter
3 : REGULAR EXPRESSION

Chapter
4: CFG

Chapter
5 : PDA

Chapter
6 : TURING MACHINE

Chapter
7 : UNDECIDIBILITY

## TU question(2066-074) solution – Click here

**Hand written notes on theory of computation **

## Finite Automata

A finite automaton is a mathematical (model) abstract machine that has a set of “states” and its “control” moves from state to state in response to external “inputs”. The control may be either “deterministic” meaning that the automation can‟t be in more than one state at any one time, or “non deterministic”, meaning that it may be in several states at once. This distinguishes the class of automata as DFA or NFA.

‐ The DFA, i.e. Deterministic Finite Automata can‟t be in more than one
state at any time.

‐ The NFA, i.e. Non-Deterministic Finite Automata can be in more than one state
at a time.

**Applications:**

The finite state machines are used in applications in computer science and data
networking. For example, finite-state machines are basis for programs for spell
checking, indexing, grammar checking, searching large bodies of text,
recognizing speech, transforming text using markup languages such as XML &
HTML, and network protocols that specify how computers communicate.

**Definition (Deterministic finite state automata [DFSA])**

A deterministic finite automaton is defined by a quintuple (5-tuple) as (Q, Σ,
δ, q0, F).

Where,

Q = Finite set of states,

Σ = Finite set of input symbols,

δ = A transition function that maps Q × Σ -> Q

q0 = A start state; q0 ∈ Q

F = Set of final states; F ⊆ Q.

A transistion function δ that takes as arguments a state and an input symbol
and returns a state. In our

diagram, δ is represented by arcs between states and the labels on the arcs.