Theory of Computability

Main Focus

What is a Computational Problem?

Problem: With some input given paired with a goal that can be determined by such input Solutions: Algorithms

How to Specify Problems?

Strings

Alphabet: A Finite Set of Symbols ( $Σ = {a, b, c}$ ) String: A Finite Sequence of Symbols (" $abba$ ")

$∣ s ∣ =$ length of a string $s$ Language: A Set of Strings (over a fixed $Σ$ )
$∣ L ∣ =$ size of Language $L$
$Σ^{*} =$ Set of all strings over $Σ$ Regular Expression: A way to describe the properties we want to test on
$R = a (a \in Σ) L (a) = {a}$
$R = ϵ =$ "" $L (ϵ) = {ϵ}$
$R = \emptyset$ $L (\emptyset) = \emptyset = {}$

Rules of Regular Expressions

R R R = R_{1} \cup R_{2} = R_{1} \cdot R_{2} = R_{1}^{*} L (R_{1} \cup R_{2}) = L (R_{1}) \cup L (R_{2}) L (R_{1} \cdot R_{2}) = {w_{1} w_{2} ∣ w_{1} \in L (R_{1}), w_{2} \in L (R_{2})} L (R_{1}^{*}) = {w_{1}, w_{2}, ..., w_{k} ∣ k \geq 0, \forall i, w_{i} \in L (R_{1})}

Numbers

$A = n$
$A = A_{1} + A_{2}$
$A = A_{1} \cdot A_{2}$
$A = A_{1}^{2}$
$A = (A_{1})$

Eval: $A$ → $N$

Example

$R = (a \cdot (a \cup b)^{*} \cdot b) \cup (b \cdot (a \cup b)^{*} \cdot b)$ → “All strings over $Σ = a, b$ that begin and end with different symbols”

w = b oo l e an s t r in g aba \in l an gu a g e L_{1}

Question: Given: $R$ , $w$ Output: $w \in L (R)$ ?

Deterministic Finite Automaton (DFA)

Definition

A DFA is a 5-tuple $M = (Q, Σ, δ, s, F)$ where:

$Q$ is a finite set of states

$Σ$ is an alphabet (finite set of symbols)

$δ$ : $Q \times Σ \to Q$ as a table of which state $q$ have an edge to with a label of $a$

$δ (q, a) \in Q$ : the function returns the destination state in $Q$

$s \in Q$ the starter state in $Q$

$F \subset Q$ the finish state(s)

The computation of DFA $M$ on input $w \in Σ^{*}$ is the sequence $q_{o}, w_{1}, q_{1}, w_{2}, q_{2}, \dots, w_{n}, q_{n}$ of $q_{i} \in Q$ and $w_{i} \in Σ$ such that

$w = w_{1} w_{2} w_{3} \dots w_{n}$
$q_{0} = s$
$q_{i + 1} = δ (q_{i}, w_{i + 1})$

There exist only 1 possible sequence

The computation is accepting if $q_{n} \in F$ The computation is rejecting if $q_{n} \neq \in F$

$δ^{*}$ : $Q \times Σ^{*} \to Q$ $δ^{*} (q, ϵ) = q$ $δ^{*} (q, a w) = δ^{*} (δ (q, a), w)$ $L (M) = w \in Σ^{*} ∣ δ^{*} (s, w) \in F)$

Jason's Notebook

Explorer

Theory of Computability

Main Focus

What is a Computational Problem?

How to Specify Problems?

Strings

Rules of Regular Expressions

Numbers

Deterministic Finite Automaton (DFA)

Are Some Problems Easier / Harder to Solve?

Are There Unsolvable Problems?

Introduction to Theory of Computability

Regular Languages

Graph View

Table of Contents