Computation Theory: Designing DFAs and NFAs for String Languages

This assignment delves into the theory of computation, focusing on the design of Deterministic Finite Automata (DFA) and Nondeterministic Finite Automata (NFA) for recognizing specific languages. It addresses four key questions, starting with the creation of DFAs for languages that either exclude or include substrings of '00' or '11'. The assignment then designs a DFA for a language with an even number of 'a's and an odd number of 'b's. Furthermore, it constructs a transition diagram for the language L= {a^(2k+1) b^(3m+2) | k,m>=0} and develops a DFA for L= {a(b)^n(a)^m: n>=3, m>=2}, providing tabular forms and explanations for each automaton. The document references relevant literature in the field of computation theory.

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.