Theory of Computation: DFA and Transition Diagrams

This article explains the Theory of Computation and its applications in computer science. It covers topics like Finite Automata, Deterministic Finite Automata (DFA), Nondeterministic Finite Automata (NFA), and Transition Diagrams. The article provides solved examples for creating DFAs and Transition Diagrams. The content is relevant for students studying computer science and related courses.

Running Head: THEORY OF COMPUTATION
THEORY OF COMPUTATION

THEORY OF COMPUTATION 1
Table of Contents
Introduction.................................................................................................................................................2
Answer to question no. 1.........................................................................................................................2
Answer to question no. 2.........................................................................................................................3
Answer to question no. 3.........................................................................................................................5
Answer to question no. 4.........................................................................................................................5
References...................................................................................................................................................7

THEORY OF COMPUTATION 2
Introduction
In the study of computer science, Theory of computation is the branch that solves the
problem of computation using various algorithms. Various machines are used to recognize the
pattern one of them is Finite Automata (FA) (Sipser, 2012). It consists of { q, ∑, q, F, δ },
Where: q : Set of finite states.
∑ : Set of Input Symbols.
q : Initial state.
F : set of Final States.
δ : Transition Function
Future, for Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA)
transition function is defined on every state (Bernardi, Mustafa, Neaton & Louie, 2015.).
Answer to question no. 1
Given L1 ⊂ ∑*, L2 ⊂ ∑*, Where ∑= {0,1}
(a) L1 should not contain substring of 00 or 11 or both
Tabular Form 0 1
q0 q1 q0
q1 q1 q2
q2 q2 q2
q3 - -

THEORY OF COMPUTATION 3
(b) L2 should contain substring of 00 or 11 or both
Tabular Form 0 1
q0 q1 q1
q1 q1 q1

THEORY OF COMPUTATION 4
Answer to question no. 2
Given, L ⊂ ∑*, where ∑= {a,b}
Creating a DFA with even numbers of a’s and odd numbers of b’s.

THEORY OF COMPUTATION 5
Using the guidelines from ( Vries, 2014 ):
Tabular Form a b
q0 q0 -
q1 q0 q2
q2 q3 q2
q3 q2 q0
For example, considering the string ‘aabbbaaaabb’ in this string there are even numbers of a’s
and odd number of b’s
In the above automata all the string with eve n number of a’s and odd numbers of b’s are
verified.
Initial state is q0 and final state is q3

THEORY OF COMPUTATION 6
Answer to question no. 3
Transition Diagram for the language L= {a^(2k+1) b^(3m+2) | k,m>=0}.
Substituting the value of k,m in the language.
We get the following string as = a(b)^2, (a)^3(b)^5, (a)^5(b)^8, (a)^3(b)^2 …
Tabular form a b
q0 q0 q1
q1 - q1
Initial state is q0 and final state is q1
Answer to question no. 4
Given L= {a(b)^n(a)^m: n>=3, m>=2}
n is greater than 3 and m is greater than 2

THEORY OF COMPUTATION 7
Thus, considering the minimum condition that n>=3 and m>=2 .
For example, this string meets minimum condition “abbbaa”
Tabular Form a b
q0 q0 -
q1 q2 q1
q2 q2 -

THEORY OF COMPUTATION 8
According to the theory of (Ruehle, et. al 2015), following DFA is drawn:
Initial state is q0 and final state is q2

THEORY OF COMPUTATION 9
References
Sipser, M., 2012. Introduction to the Theory of Computation. Cengage Learning,USA.
Ruehle, M., Kasture, U.R., Naik, V.J., Suthar, N.A. and McMillen, R.J., Intel Corp,
2015. Multithreaded DFA architecture for finding rules match by concurrently performing at
varying input stream positions and sorting result tokens. U.S. Patent 9,009,448.
Bernardi, M., Mustafa, J., Neaton, J.B. and Louie, S.G., 2015. Theory and computation of hot
carriers generated by surface plasmon polaritons in noble metals. Nature communications, 6,
p.7044.
de Vries, A., 2014. Finite automata: Behavior and synthesis(Vol. 1). Elsevier.