Notes

Prithvi Narayan Campus
Institute Of Science and Technology
Department Of Computer Science and Information
Technology
Tribhuvan University


Lab Report
On
Theory of Computation (CSC-257)

Submitted to:
Mr. Prithvi Raj Paneru

Submitted by:
Sagar Timilsina
Roll No: 27568/077


Lab Index
Name: Sagar Timilsina Roll. No: 27568/077
Level: Bachelor Year/Sem: 2nd/4th
Subject: Theory of Computation Course No.: CSC-257
SN Experiment Date of submission Remarks
1. IMPLEMENTATION OF DETERMINSTIC FINITE AUTOMATA. 2080/03/24
2. IMPLEMENTATION OF NON DETERMINSTIC FINITE AUTOMATA. 2080/03/24
3. IMPLEMENTATION OF PUSH DOWN AUTOMATA. 2080/03/24
4. IMPLEMENTATION OF PUSH DOWN AUTOMATA. 2080/03/24
5. IMPLEMENTATION OF TURING MACHINE. 2080/03/24
6. IMPLEMENTATION OF TURING MACHINE. 2080/03/24























Lab 1

TITLE: IMPLEMENTATION OF DETERMINSTIC FINITE AUTOMATA.

OBJECTIVE:
Recognize or accept a given input string based on a specified pattern or language.
Determine whether the input string satisfies the rules and constraints defined by the DFA.
Transition between different states based on the input symbols received, following a deterministic transition function.
Reach an accepting state if the input string is accepted, or a non-accepting state if the input string is rejected, based on the DFA's rules.
THEORY:
Deterministic Finite Automata is a finite-state machine that accepts or rejects strings of symbols and only produces a unique computation of the automation for each input string. In DFA, for each input symbol, one can determine a unique state to which the machine will move. It is a simplest model of computation which has a very limited memory.
The formal definition of DFA is defined as 5 – tuples D = {Q, ∑ , δ, qo , F} where,

Q is set of finite states,
∑ is set of finite symbols,
δ is a transition function which takes a state as an output.
δ:Q* ∑ Q
qo : Start State,
F is set of final state also called accepting state F ⊂ Q.

PROGRAM: C program to implement the Determinstic Finite Automata.
Source code:
Output:

CONCLUSION:












Lab 2

TITLE: IMPLEMENTATION OF NON-DETERMINISTIC FINITE AUTOMATA.
OBJECTIVE:
Recognize or accept a given input string based on a specified pattern or language.
Determine whether the input string satisfies the rules and constraints defined by the NFA.
Transition between different states according to the input symbols received.
Reach an accepting state if the input string is accepted by following the NFA's transition function.

THEORY:
Non-Deterministic Finite Automata is a finite-state machine that accepts or rejects strings of symbols and can move to any combination of the states in the machine.
The formal definition of NFA is defined as 5 – tuples D = {Q, ∑ , δ, qo , F} where,

Q is set of finite states,
∑ is set of finite symbols,
δ is a transition function that maps state symbol pair to sets of states,
δ:Q* ∑ 2Q
q0: Start State,
F: Set of final state also called accepting state F ⊂ Q.



PROGRAM:
Source code:
Output:


CONCLUSION:











Lab 3
TITLE: IMPLEMENTATION OF DETERMINISITIC PUSH DOWN AUTOMATA.
OBJECTIVE:
Recognize or accept a given input string based on a specified pattern or language.
Utilize a stack to handle and track the input symbols and perform additional computations.
Determine whether the input string satisfies the rules and constraints defined by the DPDA, considering both the input symbols and the stack contents.
Transition between different states based on the input symbols received and the top symbol of the stack, following the DPDA's transition rules and stack operations.

THEORY:
A pushdown automata is said to be deterministic if for every input alphabet ‘a’ (a may be ∈) and top of stack symbol, PDA has either unique transition (i.e moves to only one state.) or its transition is not defined. Formally, A pushdown automata is defined by seven tuples as
P = {Q, ∑, Γ, δ, q0, Z0, F)
Where, Q is a set of finite states,
∑ is a set of finite symbols,
Γ is finite set of stack symbols,
q0 is a start state, q0 ε Q
Z0 is a initial stack symbol, Z0 ε Γ
F is a set of final states, F ⊂ Q,
δ is a transition function which is of the form δ(q,a,X) = (p, α)
Where p, q are states a is an input symbol or ε
X is stack symbol
α is stack string α ε Γ
is deterministic pushdown automata if the following two conditions are statisfied.
For any q ε Q, X ε Γ,
if δ(q,a,X) ≠ ∅ for any a ε ∑ then δ(q,ε,X) = ∅
i.e if δ(q,a,X) is non-empty for some a, then δ(q,ε,X) must be empty.

For any q ε Q, a ε ∑ ∪{ ε} and X ε Γ,
δ(q,a,X) has at most one element.



PROGRAM:
Source code:
Output :


CONCLUSION:




Lab 4

TITLE: IMPLEMENTATION OF NON-DETERMINISITIC PUSH DOWN AUTOMATA.
OBJECTIVE:
Recognize or accept a given input string based on a specified pattern or language.
Utilize a stack to handle and track the input symbols and perform additional computations.
Explore multiple possible paths simultaneously during the computation, allowing for greater expressive power and flexibility in language recognition.
Determine whether the input string satisfies the rules and constraints defined by the NPDA, considering both the input symbols and the stack contents, while allowing for nondeterministic choices during state transitions.

THEORY:
A non-deterministic pushdown automata is basically an NFA with a stack added to it. Formally, A pushdown automata is defined by seven tuples as
P = {Q, ∑, Γ, δ, q0, Z0, F}
Where, Q is a set of finite states,
∑ is a set of finite symbols,
Γ is finite set of stack symbols,
q0 is a start state, q0 ε Q
Z0 is a initial stack symbol, Z0 ε Γ
F is a set of final states, F ⊆ Q,
δ is a transition function that maps
Q × (∑ ∪{λ}) × Γ* → finite subsets of Q × Γ*


PROGRAM:
Source code:
Output:
CONCLUSION:















Lab 5
TITLE: IMPLEMENTATION OF TURING MACHINE.
OBJECTIVE:
Compute or process input strings according to a specified algorithm or set of rules.
Perform complex computations and solve a wide range of computational problems.
Recognize and accept a given language or set of strings.
Simulate the concept of an algorithmic computation, providing a formal and theoretical model of computation.

THEORY:
A turing Machine is a finite automation with a two-way access to an infinite tape. Turing machine, which is a simple model of a real computer. Turing machines can be used to accept all context-free languages. Every problem that can be solved on a real computer can also be solved by a Turing machine. Formal Definition of Turing Machine is:
A Turing machine TM is defined by the seven tuples , M = {Q, ∑, Γ, δ, q0, B , F} where,