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.
