$$ \def\empty{\mathcal E} \def\length#1{\left\lvert#1\right\rvert} \def\accepts{,\text{accepts},} \def\if{,\text{if},} \def\N{\mathbb N} $$

CS252

GNU General Public License v3.0 licensed. Source available on github.com/zifeo/EPFL.

Spring 2015: Theory of Computation

[TOC]

Automata

Finite automaton (DFA)

states with conditions and starting/accepting elements
fixed object : not allowed to depend on input size
formal definition : $M={Q,\Sigma,\delta,q_0,F}$
- $Q$ : finite set of states
- $\Sigma$ : alphabet (i.e. ${0,1}$ mostly)
- $\delta(q, a):Q\times\Sigma\to Q$ : transition function with $q\in Q$ and $a\in\Sigma$
- $q_0\in Q$ : starting state
- $F\subseteq Q$ : accepting states (finite)
extended transition function : $\hat\delta(q,ab)=\delta(\delta(q,a),b)$ with with $q\in Q$, $a\in\Sigma^*$ and $b\in\Sigma$
- $\hat\delta(s,x)=\delta(\ldots\delta(\delta(s,x_1),x_2)\ldots)$ with $s$ being a starting state and $x$ being a string

Non-deterministic automaton (NFA)

non-determinism : can be at multiple state at the same time
powerset : $2^{{0,1}^*}={\emptyset,0,1,00,01,10,11,\ldots}$
formal definition : $M={Q,\Sigma,\Delta,S,F}$
- $Q$ : finite set of states
- $\Sigma$ : alphabet (i.e. ${0,1}$ mostly)
- $\Delta(q, a):Q\times\Sigma\to 2^Q$ : transition function with $q\in Q$ and $a\in\Sigma$
- $S\subseteq Q$ : starting states (finite)
- $F\subseteq Q$ : accepting states (finite)
extended transition function : $\hat\Delta(A,x)$ with $A\subseteq Q$ and $x=a_1a_2\ldots a_n\in\Sigma^*$
- $\hat\Delta(A,\Sigma)=A$
- $\hat\Delta(A,xa)=\bigcup_\limits{q\in\hat\Delta(A,x)}\delta(q,a)$ with $x\in\Sigma^*$ and $a\in\Sigma$
accepting criteria : $x\in L(M) \iff \hat\Delta(S,x)\cap F\not=\emptyset$ with $x\in\Sigma^*$
empty transition $\epsilon$ : allow states flexibility
NFA to DFA : if $N$ is a NFA then there is a DFA $M$ such that $L(N)=L(M)$
- use transition function to generate all states unions
- lemma : $\hat\delta_M(A,x)=\hat\Delta_N(A,x)\subseteq Q_N$ (by induction)
- $Q_M=2^{Q_N}$ : but keep only the ones that are accessible
- $\delta(T,a)=\bigcup_\limits{q\in T}\Delta(q,a)$
- $S_M=S_N$ : all states containing NFA starting states
- $F_M={T\in Q_M:;T\cap F_N\not=\emptyset}$ : all states containing NFA accepting states

Turing machines

Deterministic Turing Machine (TM)

one tape with a head pointing on the current state
allow to make progress in both direction
formal definition : $M={Q,\Sigma,\Gamma,\delta,q_0,q_A,q_R}$
- $Q$ : finite set of states
- $\Sigma$ : input alphabet with $\sqcup\not\in\Sigma$
- $\Gamma$ : tape alphabet with $\sqcup\in\Gamma$ and $\Sigma\subseteq\Gamma$
- $\delta : Q\times\Gamma\to Q\times\Gamma'\times{L,R,W}$ : with $\Gamma'$ the letter to be write and $L,R,W$ stands for left, right and wait
- $q_0\in Q$ : starting state
- $q_A\in Q$ : accepting state (finite)
- $q_R\in Q$ : rejecting state (finite)
starting configuration : $tape =q_0w_1w_2\cdots\sqcup^\infty$ with $q_0$ being the head
running configuration (at any moment} : $head=UqV$ where $U=w_1\cdots w_iw_j$ being last character read on the tape and $V=w_k\cdots\sqcup^\infty$ with $w_j$
progress : $C_1\xrightarrow[M]{1}C_2\xrightarrow[M]{1}\cdots\xrightarrow[M]{1}C_R$
halts on input $w$ only
- if $q\in q_A$, $M$ accepts $w$
- if $q\in q_R$, $M$ rejects $w$
describe by tape pseudocode (with subroutines)
set of all Turing machine : countable
multi $n$ tapes
- $\delta : Q\times\Gamma^n\to Q\times\Gamma^n\times {L,R,W}$
- can be reduce to a single tape by adjusting transistion function and concatenate tapes (using marker heads)
Church thesis : no computer has more power than Turing machines
$$ denotes the encoding of $B$ (could be a Turing machine or an automaton)

can take the encoding of another Turing machine and run it on a specified input

Non-deterministic Turing Machine (NTM)

multiple branch at the same time

formal definition : $M={Q,\Sigma,\Gamma,\delta,q_0,q_A,q_R}$

$Q$ : finite set of states

$\Sigma$ : input alphabet with $\sqcup\not\in\Sigma$

$\Gamma$ : tape alphabet with $\sqcup\in\Gamma$ and $\Sigma\subseteq\Gamma$

$\delta : Q\times\Gamma\to 2^{Q\times\Gamma'\times{L,R,W}}$ : with $\Gamma'$ the letter to be write and $L,R,W$ stands for left, right and wait

$q_0\in Q$ : starting state

$q_A\in Q$ : accepting state (finite)

$q_R\in Q$ : rejecting state (finite)

computation trees (deciders) : all possible combinations

Language

Regularity

string : $\sigma\in\Sigma^*$

empty string : $\empty$

regular language : set of string accepted by $L(M)$

irregular language : no $M$ such that $L(M)=A={0^n1^n:;n\ge 0}\subseteq\Sigma^*$

complement : $\overline{L(M)}=\Sigma^*-L(M)$ by inverting accepting states (i.e. $F'=Q-F$)

regularity for languages $A,A_1,A_2$ over

union : $A_1\cup A_2={\sigma:;\sigma\in A_1\lor\sigma\in A_2}$

$Q=Q_1\times Q_2$

$q_0=(q_1,q_2)$

$\delta((q_i,q_j), a)=(\delta(q_i,a),\ delta(q_j,a))$

$F=(F_1\times Q_2)\cup(Q_1\times F_2)$

intersection : $A_1\cap A_2={\sigma:;\sigma\in A_1\land\sigma\in A_2}$

concatenation : $A_1\circ A_2={\sigma_1\sigma_2:;\sigma_1\in A_1,;\sigma_2\in A_2}$

complement $\bar A={\sigma\in\Sigma^*:;\sigma\not\in A}$

pumping lemma

if $A$ is a regular language then $\exists p\ge 0$ (called the pumping length) such that if $\sigma\in A$ and $\length{\sigma}\ge p$ then $\sigma = xyz$

$xy^iz\in A \forall i \ge 0$

$\length{xy}\le p$

$\length y \ge 1$

intersection $A=B\cap C$ : if $B$ is irregular and $C$ regular, then $A$ is irregular

set of all language $\Sigma^*$ : uncountable

Decidability

Turing decidable language $A$ (recursive language) : if $\exists M$ (a Turing machine) such that

$M(w)\downarrow$ : always halts

$M(w)=yes\iff w\in A$ or $A=L(M)={\omega : M\accepts\omega}$

undeciabability

take $A_{TM}={<M,\omega> : M\accepts\omega}$

assume $H(M)={<M,> : M\accepts\text{its encoding}}$ such that $H$ decide $A_{TM}$ (halts)

construct a decider $D(M)$ : run $H(M)$ and if $H$ accepts, $D$ rejects or if $H$ rejects, $D$ accepts

run $D(D)$

$D$ accepts $$ only if $H$ rejects $<D, >$ but that only happen when $D$ rejects $$

$D$ rejects $$ only if $H$ accepts $<D, >$ but that only happen when $D$ accepts $$

Recognisability

Turing recognizable language $A$ (semi-recursivelanguage) : if $\exists M$ (a Turing machine) such that

if $w\in A$, $M(w)=yes$

if $w\not\in A$, either $M(w)\uparrow$ (loops) or $M(w)=no$

$L$ and $\overline L$ recognizable $\iff$ $L$ dedicable

let $M_1$ and $M_2$ recognize $L$ and its complements

construct a machine $P$ that runs $M_1$ and $M_2$ in parallel

if $M_1$ accepts, $P$ returns $yes$

if $M_2$ accepts, $P$ returns $no$

by definition $P$ decide $L$

Reduction $\le_M$

computable function : $f : \Sigma^*\to\Sigma^ *$ if there is a Turing machine which stops on input $w$ with $f(w)$ on its output tape

Turing reductible $A\le_M B$: a language $A$ is Turing reductible to $B$ if there is a computable function such that $\forall w\in\Sigma^*$ we have $w\in A\iff f(w)\in B$

Time complexity

worst case complexity : $t(n)$

Big-O : $f(n)=O(g(n))\iff \exists c,n_0\text{ such that }\forall n\ge n_0; f(n)\le c g(n)$

time complexity: let $t:\N\to\N$, for a Turing machine $M$ (that halts on all inputs) has worst-case time complexity $O(t(n))$ if $\forall w\in\Sigma^*$ we have $\length{w}=n$

algorithms

$A={0^n1^n : n\ge 1 }$

check $0^*1^ *$, cross one $0$ and one $1$, check crosses : $O(n^2)$

split 0s ans 1s : $O(n)$

BFS/DFS : $t(n)=\length{m}\length{n}$

is there a cycle such that all vertices are present at least once on the cycle

Eulerian iff degrees of every V is even : $\in P$ (same as counting degree)

if $t(n)$ is the time for solving on $k$-tapes, single tape implementation is in $O(t(n)\log(t(n)))$

time complexity $1$-tape : $TIME(t(n))={L : \exists \text{ TM }M\text{ such that }M\text{ decides }L\text{ in }O(t(n))\text{ time}}$

non-deterministic time complexity : $NTIME(t(n))$ length of longest path of computation trees of NTM

polynomial time verifier $V(w\in L, c=PATH)$ : can verify proposition or $L\in NP$ if there is a NTM which take $n^k$ time

Polynomial : $P=\cup_{k\ge 0} TIME(n^k)$

Non-deterministic Polynomial : $NP={\text{all languages for which there is a polytime verifer}}=\cup_{k\ge 0} NTIME(n^k)$

NP-Completeness : a language is said to be NP-Complete if $L\in NP$ and $\forall A\in NP;A\le_p L$

Exponential : $EXPTIME=\cup_{k\ge 0} TIME(2^{n^k})$

$P\subseteq NP$ but is the inverse true ?

Cook-Levin theorem : if $SAT\in P \Rightarrow P=NP$

NP-hardness : if finding a solution for $L$ means $P=NP$

Reduction $\le_P$

polytime function : the mapping can be done in polynomial time

polytime reduction $A\le_P B$ : a language $A$ is polytime reductible to $B$ if there is a computable and polytime function such that $\forall w\in\Sigma^*$ we have $w\in A\iff f(w)\in B$ (completeness & soundness)

Space complexity

how much tape is used as a fonction of $n$ in the worst case

space complexity : a language $L$ is accepted by a TM which uses $f(n)$ space on inputs of size $n$ is in $SPACE(f(n))$

non-deterministic space complexity : a language $L$ is accepted by a NTM which uses $f(n)$ space on inputs of size $n$ is in $NSPACE(f(n))$

$PSPACE=\cup_{k\ge 0} SPACE(n^k)$

$NSPACE=\cup_{k\ge 0} NSPACE(n^k)$

$NP\subseteq PSPACE \subseteq NSPACE$

all configuration of a TM hold in less that $|\Sigma|^{n^2}\approx 2^{nk}$ : $PSPACE\subseteq EXPTIME$

Savitch theorem : $PSPACE=NSPACE$ (NTM are powerless)

relation between space and time complexity

Problem indexes

P

EULERIANPATH (undirected graph) : is there a cycle such that all vertices are present at least once on the cycle ? Eulerian iff the degrees of every vertex is even

NP-Complete

CLIQUE (undirected graph) : has a clique (complete subgraph) of size $k$

**3SAT : is there an assignment that satifies $(x_1\vee \overline{x_2}\vee x_3)\wedge\cdots\wedge(x_4\vee x_2\vee \overline{x_3})$ where there is $n$ vars and $m$ clauses

SAT : 3SAT but without 3-place clauses constrain

VERTEXCOVER : has a vertex cover (i.e. all edges are reached) of size $k$

SUBSETSUM

HAMPATH (directed graph) : is there a hamiltonian path (i.e. visit each vertex only once) from $s$ to $t$

Co-NP

$\overline{HAMPATH}$ : no polytime verfier

Language indexes

Regular

Non-regular

$A={0^n1^n : n\ge 1 }$

$B={\sigma : \text{# of 0s = # of 1s}}$ : contains $A$ under intersection

Decidable

$A={<D, w> : \if D\accepts w}$

$B={ : L(D)\not=\emptyset}$

$EQ={<D_1,D_2> : D_1,D_2\text{ are DFAs }\wedge L(D_1)=L(D_2)}$ : check for empty symmetric difference

undecidable but recognisable

$A_{TM}={<M,\omega> : M\accepts\omega}$

$HALT={<M,w> : M(w)\downarrow }$

$REG={ : L(M)\text{ is regular}}$

unrecognisable

$\overline{A_{TM}}={<M,\omega> : M\text{ doesn't accept }\omega}\cup{\text{bad encodings}}$

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

cs252.md

cs252.md

CS252

Automata

Finite automaton (DFA)

Non-deterministic automaton (NFA)

Turing machines

Deterministic Turing Machine (TM)

Non-deterministic Turing Machine (NTM)

Language

Regularity

Decidability

Recognisability

Reduction $\le_M$

Time complexity

Reduction $\le_P$

Space complexity

Problem indexes

P

NP-Complete

Co-NP

Language indexes

Regular

Non-regular

Decidable

undecidable but recognisable

unrecognisable

Files

cs252.md

Latest commit

History

cs252.md

File metadata and controls

CS252

Automata

Finite automaton (DFA)

Non-deterministic automaton (NFA)

Turing machines

Deterministic Turing Machine (TM)

Non-deterministic Turing Machine (NTM)

Language

Regularity

Decidability

Recognisability

Reduction $\le_M$

Time complexity

Reduction $\le_P$

Space complexity

Problem indexes

P

NP-Complete

Co-NP

Language indexes

Regular

Non-regular

Decidable

undecidable but recognisable

unrecognisable