Theory of Computation: DFA and Transition Diagrams

Running Head:

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

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 - -