Blog

Thoery of computation notes

thoery of computation notes

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

Click here to get the file

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.