EOTTOC.lyx

#LyX 2.0 created this file. For more info see http://www.lyx.org/
\lyxformat 413
\begin_document
\begin_header
\textclass scrbook
\use_default_options true
\maintain_unincluded_children false
\language english
\language_package default
\inputencoding auto
\fontencoding global
\font_roman default
\font_sans default
\font_typewriter default
\font_default_family default
\use_non_tex_fonts false
\font_sc false
\font_osf false
\font_sf_scale 100
\font_tt_scale 100

\graphics default
\default_output_format default
\output_sync 0
\bibtex_command default
\index_command default
\paperfontsize default
\spacing single
\use_hyperref true
\pdf_bookmarks true
\pdf_bookmarksnumbered false
\pdf_bookmarksopen false
\pdf_bookmarksopenlevel 1
\pdf_breaklinks false
\pdf_pdfborder false
\pdf_colorlinks false
\pdf_backref false
\pdf_pdfusetitle true
\papersize default
\use_geometry false
\use_amsmath 1
\use_esint 1
\use_mhchem 1
\use_mathdots 1
\cite_engine basic
\use_bibtopic false
\use_indices false
\paperorientation portrait
\suppress_date false
\use_refstyle 1
\index Index
\shortcut idx
\color #008000
\end_index
\secnumdepth 3
\tocdepth 3
\paragraph_separation indent
\paragraph_indentation default
\quotes_language english
\papercolumns 1
\papersides 1
\paperpagestyle default
\tracking_changes false
\output_changes false
\html_math_output 0
\html_css_as_file 0
\html_be_strict false
\end_header

\begin_body

\begin_layout Title
Reading Notes of
\begin_inset Newline newline
\end_inset

Elements of the Theory of Computation
\end_layout

\begin_layout Author
Tianyi Cui
\end_layout

\begin_layout Date
\begin_inset ERT
status open

\begin_layout Plain Layout


\backslash
today
\end_layout

\end_inset


\end_layout

\begin_layout Chapter*
Introduction
\end_layout

\begin_layout Standard
Fundamental questions in computer science answered by theory of computation:
\end_layout

\begin_layout Itemize
What is an algorithm? 
\end_layout

\begin_layout Itemize
What can and what cannot be computed?
\end_layout

\begin_layout Itemize
When should an algorithm be considered practically feasible.
\end_layout

\begin_layout Standard
The theory of computation is the mathematical abstractions of computers,
 but its origin is even before the advent of the electronic computer.
\end_layout

\begin_layout Quote
It is based on very few and elementary concepts, and draws its power and
 depth from the careful, patient, extensive, layer-by-layer manipulation
 of these concepts -- just like the computer.
 
\end_layout

\begin_layout Chapter
Sets, Relations, and Languages
\end_layout

\begin_layout Section
Sets
\end_layout

\begin_layout Standard
Power set: 
\begin_inset Formula $2^{A}$
\end_inset

, the collection of all subsets of set 
\begin_inset Formula $A$
\end_inset

.
\end_layout

\begin_layout Standard
Partition of set 
\begin_inset Formula $A$
\end_inset

, subset of 
\begin_inset Formula $2^{A}$
\end_inset

 whose elements are nonempty and disjoint when contain all elements of 
\begin_inset Formula $A$
\end_inset

.
\end_layout

\begin_layout Section
Relations and functions
\end_layout

\begin_layout Standard
\begin_inset Formula $a$
\end_inset

 and 
\begin_inset Formula $b$
\end_inset

 are called the 
\emph on
components
\emph default
 of the ordered pair 
\begin_inset Formula $(a,b)$
\end_inset

.
\end_layout

\begin_layout Standard
The 
\emph on
Cartesian product
\emph default
 of two sets.
\end_layout

\begin_layout Standard
Ordered tuples: ordered triples, quadruples, quintuples, sextuples...
\end_layout

\begin_layout Standard
\begin_inset Formula $n$
\end_inset

-ary relation: unary, binary, ternary...
\end_layout

\begin_layout Standard
The domain, image, 
\emph on
range
\emph default
, of function; one-to-one + onto = bijection; inverse.
\end_layout

\begin_layout Section
Special types of binary relations
\end_layout

\begin_layout Standard
The relation 
\begin_inset Formula $R\in A\times A$
\end_inset

 is called a 
\emph on
directed graph
\emph default
.
\end_layout

\begin_layout Standard
Properties of relations: reflexive, symmetric, antisymmetric, transitive.
\end_layout

\begin_layout Standard
Equivalence relation: r, s, t.
 Partial order: r, a, t.
 Total order.
\end_layout

\begin_layout Section
Finite and infinite sets
\end_layout

\begin_layout Standard
Call two sets 
\emph on
equinumerous
\emph default
 if there is a bijection between them.
\end_layout

\begin_layout Standard
Finite (equinumerous with 
\begin_inset Formula $\{{1,2,\ldots n}\}$
\end_inset

, infinite, countably infinite (equinumerous with 
\begin_inset Formula $\mathbf{{N}}$
\end_inset

), countable, uncountable.
 
\end_layout

\begin_layout Section
Three fundamental proof techniques
\end_layout

\begin_layout Standard
The Principle of Mathematical Induction: Let 
\begin_inset Formula $A$
\end_inset

 be a set of natural numbers such that (1) 
\begin_inset Formula $0\in A$
\end_inset

, and (2) for each natural number 
\begin_inset Formula $n$
\end_inset

`$n$`, if 
\begin_inset Formula $\{0,1,\ldots,n\}\subseteq A$
\end_inset

, then 
\begin_inset Formula $n+1\in A$
\end_inset

.
 Then 
\begin_inset Formula $A=\mathbf{N}$
\end_inset

.
\end_layout

\begin_layout Standard
The Pigeonhole Principle: if 
\begin_inset Formula $A$
\end_inset

 and 
\begin_inset Formula $B$
\end_inset

 are finite sets and 
\begin_inset Formula $|A|>|B|$
\end_inset

, then there is no one-to-one function from 
\begin_inset Formula $A$
\end_inset

 to 
\begin_inset Formula $B$
\end_inset

.
\end_layout

\begin_layout Standard
The Diagonalization Principle: Let 
\begin_inset Formula $R$
\end_inset

 be a binary relation on a set 
\begin_inset Formula $A$
\end_inset

, and let 
\begin_inset Formula $D$
\end_inset

, the diagonal set for 
\begin_inset Formula $R$
\end_inset

, be 
\begin_inset Formula $\{a:a\in A\text{ and }(a,a)\notin R\}$
\end_inset

.
 For each 
\begin_inset Formula $a\in A$
\end_inset

, let 
\begin_inset Formula $R_{a}=\{b:b\in A\text{ and }(a,b)\in R\}$
\end_inset

.
 Then 
\begin_inset Formula $D$
\end_inset

 is distinct from each 
\begin_inset Formula $R_{a}$
\end_inset

.
 Lemma: the set 
\begin_inset Formula $2^{\mathbf{N}}$
\end_inset

 is uncountable.
 
\end_layout

\begin_layout Section
Closures and algorithms
\end_layout

\begin_layout Standard
The 
\emph on
reflexive transitive closure
\emph default
 of a directed graph.
\end_layout

\begin_layout Standard
The 
\emph on
rate of growth
\emph default
 of a function 
\begin_inset Formula $f$
\end_inset

 on 
\begin_inset Formula $\mathbf{{N}}$
\end_inset

.
\end_layout

\begin_layout Standard
The proof of correctness of the Floyd algorithm: define 
\emph on
rank of a path
\emph default
 as the biggest index among its intermediate nodes, and prove that after
 the 
\begin_inset Formula $j$
\end_inset

th iteration, all path with rank less than or equal to 
\begin_inset Formula $j$
\end_inset

 will be found.
\end_layout

\begin_layout Standard
Closure property: Let 
\begin_inset Formula $D$
\end_inset

 be a set, let 
\begin_inset Formula $n\geq0$
\end_inset

, and let 
\begin_inset Formula $R\subseteq D^{n+1}$
\end_inset

 be a 
\begin_inset Formula $(n+1)$
\end_inset

-ary relation on 
\begin_inset Formula $D$
\end_inset

.
 Then a subset 
\begin_inset Formula $B$
\end_inset

 of 
\begin_inset Formula $D$
\end_inset

 is said to be 
\emph on
closed under
\emph default
 
\begin_inset Formula $R$
\end_inset

 if 
\begin_inset Formula $b_{n+1}\in B$
\end_inset

 whenever 
\begin_inset Formula $b_{1},\ldots,b_{n}\in B$
\end_inset

 and 
\begin_inset Formula $(b_{1},\ldots,b_{n},b_{n+1}\}\in R$
\end_inset

.
 Any property of the form "the set 
\begin_inset Formula $B$
\end_inset

 is closed under relation 
\begin_inset Formula $R_{1},R_{2},\ldots,R_{m}$
\end_inset

" is called a 
\emph on
closure property
\emph default
 of 
\begin_inset Formula $B$
\end_inset

.
\end_layout

\begin_layout Standard
The minimal set 
\begin_inset Formula $B$
\end_inset

 that contains 
\begin_inset Formula $A$
\end_inset

 and has property 
\begin_inset Formula $P$
\end_inset

 is unique if 
\begin_inset Formula $P$
\end_inset

 is a closure property defined by relations on a set 
\begin_inset Formula $D$
\end_inset

 while 
\begin_inset Formula $A\subseteq D$
\end_inset

.
 Then we call 
\begin_inset Formula $B$
\end_inset

 the 
\emph on
closure
\emph default
 of 
\begin_inset Formula $A$
\end_inset

 under the relation 
\begin_inset Formula $R_{1},\ldots,R_{m}$
\end_inset

.
\end_layout

\begin_layout Standard
Inclusion property: unary closure (take 
\begin_inset Formula $n=0$
\end_inset

 in definition).
\end_layout

\begin_layout Standard
Any closure property over a finite set can be computed in polynomial time
 (see ex1.6.9).
 
\end_layout

\begin_layout Section
Alphabets and languages
\end_layout

\begin_layout Standard
Here is the 
\emph on
mathematics of strings of symbols
\emph default
.
\end_layout

\begin_layout Description
symbol: any object, but often only common characters are used.
\end_layout

\begin_layout Description
alphabet: a finite set of symbols.
\end_layout

\begin_layout Description
string: finite sequence of symbols from the alphabet, which has 
\emph on
length
\emph default
, operation of 
\emph on
concatenation
\emph default
(
\begin_inset Formula $\circ$
\end_inset

), 
\emph on
substring
\emph default
, 
\emph on
prefix
\emph default
, 
\emph on
suffix
\emph default
, 
\begin_inset Formula $s^{n}$
\end_inset

, operation of 
\emph on
reversal
\emph default
(
\begin_inset Formula $s^{R}$
\end_inset

) defined
\end_layout

\begin_layout Description
language: any set of strings over an alphabet 
\begin_inset Formula $\Sigma$
\end_inset

, that is, any subset of 
\begin_inset Formula $\Sigma^{*}$
\end_inset

.
 It might be able to be enumerated 
\emph on
lexicographically
\emph default
.
 It has 
\emph on
complement
\emph default
 (
\begin_inset Formula $\overline{L}$
\end_inset

), 
\emph on
concatenation of languages
\emph default
, 
\emph on
Kleene star
\emph default
 (the set of all strings obtained by concatenating zero or more strings
 from it).
 We write 
\begin_inset Formula $L^{+}$
\end_inset

 for 
\begin_inset Formula $LL^{*}$
\end_inset

, which is the 
\emph on
closure
\emph default
 of 
\begin_inset Formula $L$
\end_inset

 under the function of concatenation.
\end_layout

\begin_layout Section
Finite representations of languages
\end_layout

\begin_layout Standard
This section discusses how to use 
\emph on
regular expressions
\emph default
 to represent languages.
\end_layout

\begin_layout Standard
A 
\emph on
regular expression
\emph default
 is the representation of language using empty set, characters in alphabet,
 concatentaion (symbol usually omitted), function of union (the 
\emph on
or
\emph default
 operator in regex), star, and parentheses.
 We can define the function 
\begin_inset Formula $\mathcal{L}$
\end_inset

 from regular expressions to lanuages, whose range is called the class of
 
\emph on
regular languages
\emph default
.
\end_layout

\begin_layout Standard
A 
\emph on
language recognition device
\emph default
 is an algorithm that is specifically designed to answer questions of the
 form "is string 
\begin_inset Formula $w$
\end_inset

 a member of 
\begin_inset Formula $L$
\end_inset

?".
\end_layout

\begin_layout Standard
A 
\emph on
language generator
\emph default
 is the description of the way of generating members of a language.
\end_layout

\begin_layout Standard
The relation between the above two types of finite language specifications
 is another major subject of this book.
\end_layout

\begin_layout Chapter
Finite Automata
\end_layout

\begin_layout Section
Deterministic Finite Automata
\end_layout

\begin_layout Standard
DFA is computer with no memory; input a string, output indicate whether
 it's acceptable.
 
\end_layout

\begin_layout Standard
DFA definition: quintuple 
\begin_inset Formula $M=(K,\Sigma,\delta,s,F)$
\end_inset

, where 
\begin_inset Formula $K$
\end_inset

 is a finite set of 
\emph on
states
\emph default
, 
\begin_inset Formula $\Sigma$
\end_inset

 is an alphabet, 
\begin_inset Formula $s\in K$
\end_inset

 is the 
\emph on
initial state
\emph default
, 
\begin_inset Formula $F\subseteq K$
\end_inset

 is the set of 
\emph on
final states
\emph default
, and 
\begin_inset Formula $\delta$
\end_inset

 the 
\emph on
transition function
\emph default
, is a function from 
\begin_inset Formula $K\times\Sigma$
\end_inset

 to 
\begin_inset Formula $K$
\end_inset

.
\end_layout

\begin_layout Standard
A 
\emph on
configuration of a DFA
\emph default
 is any elements of 
\begin_inset Formula $K\times\Sigma^{*}$
\end_inset

.
 For two configuration 
\begin_inset Formula $(q,w)$
\end_inset

 and 
\begin_inset Formula $(q',w')$
\end_inset

, then 
\begin_inset Formula $(q,w)\vdash_{M}(q',w')$
\end_inset

 if and only if 
\begin_inset Formula $w=aw'$
\end_inset

 for some symbol 
\begin_inset Formula $a\in\Sigma$
\end_inset

, and 
\begin_inset Formula $\delta(q,a)=q'$
\end_inset

.
 We say that 
\begin_inset Formula $(q,w)$
\end_inset

 
\series bold
yields
\series default
 
\begin_inset Formula $(q',w')$
\end_inset

 
\series bold
in one step
\series default
.
 Denote the reflexive transitive closure of 
\begin_inset Formula $\vdash_{M}$
\end_inset

 by 
\begin_inset Formula $\vdash_{M}^{*}$
\end_inset

, 
\begin_inset Formula $(q,w)$
\end_inset

 
\begin_inset Formula $\vdash_{M}^{*}$
\end_inset

 
\begin_inset Formula $(q',w')$
\end_inset

 is read, 
\begin_inset Formula $(q,w)$
\end_inset

 
\series bold
yields
\series default
 
\begin_inset Formula $(q',w')$
\end_inset

.
\end_layout

\begin_layout Standard
A string 
\begin_inset Formula $w\in\Sigma^{*}$
\end_inset

 is said to be 
\emph on
accepted
\emph default
 by 
\begin_inset Formula $M$
\end_inset

 if and only if there is a state 
\begin_inset Formula $q\in F$
\end_inset

 such that 
\begin_inset Formula $(s,w)\vdash_{M}^{*}(q,e)$
\end_inset

.
 
\emph on
The language accepted
\emph default
 by 
\begin_inset Formula $M$
\end_inset

, 
\begin_inset Formula $L(M)$
\end_inset

 is the set of all strings accepted by 
\begin_inset Formula $M$
\end_inset

.
\end_layout

\begin_layout Section
Nondeterministic Finite Automata
\end_layout

\begin_layout Standard
NFAs are simply a useful 
\emph on
notational generalization
\emph default
 of finite automata, as they can greatly simplify the description of these
 automata.
 Moreover, every NFA is equivalent to a DFA.
\end_layout

\begin_layout Standard
NFA definition: quintuple 
\begin_inset Formula $M=(K,\Sigma,\Delta,s,F)$
\end_inset

 where 
\begin_inset Formula $\Delta$
\end_inset

 the 
\emph on
transition relation
\emph default
, is a subset of 
\begin_inset Formula $K\times(\Sigma\cup\{e\})\times K$
\end_inset

.
 Each triple 
\begin_inset Formula $(q,u,p)\in\Delta$
\end_inset

 is called a 
\emph on
transition
\emph default
 of 
\begin_inset Formula $M$
\end_inset

.
\end_layout

\begin_layout Standard
Two finite automata 
\begin_inset Formula $M_{1}$
\end_inset

 and 
\begin_inset Formula $M_{2}$
\end_inset

 are 
\emph on
equivalent
\emph default
 if and only if 
\begin_inset Formula $L(M_{1})=L(M_{2})$
\end_inset

.
 For each NFA, there is an equivalent DFA.
\end_layout

\begin_layout Section
Finite Automata and Regular Expressions
\end_layout

\begin_layout Standard
The class of languages accepted by DFA or NFA, is the same as the class
 of 
\emph on
regular languages
\emph default
 -- those that can be described by regular expressions.
\end_layout

\begin_layout Standard
The class of regular languages are the closure of certain finite languages
 under the language operations of union, concatenation, and Kleene star.
 We can prove similar closure properties of the class of languages accepted
 by finite automata: union, concatenation, Kleene star, complementation
 (exchange the final and nonfinal states), intersection (represented as
 complementation and union).
 Therefore, a language is regular 
\emph on
only if
\emph default
 it is accepted by a finite automaton.
\end_layout

\begin_layout Standard
The other part, a language is regular
\emph on
 if
\emph default
 it is accepted by a finite automaton, can be proved by constructing a regular
 expression from every NFA.
 The way is to find all paths between initial state to some final state,
 then union them.
\end_layout

\begin_layout Section
Languages that are and are not Regular
\end_layout

\begin_layout Standard
Showing languages are regular: use regular expressions or automata and operation
s on languages.
\end_layout

\begin_layout Standard
Theorem (one of 
\emph on
pumping theorems
\emph default
): Let 
\begin_inset Formula $L$
\end_inset

 be a regular language.
 There is an integer 
\begin_inset Formula $n\geq1$
\end_inset

 such that any string 
\begin_inset Formula $w\in L$
\end_inset

 with 
\begin_inset Formula $|w|\geq n$
\end_inset

 can be rewritten as 
\begin_inset Formula $w=xyz$
\end_inset

 such that 
\begin_inset Formula $y\not=e$
\end_inset

, 
\begin_inset Formula $|xy|\leq n$
\end_inset

, and 
\begin_inset Formula $xy^{i}z\in L$
\end_inset

 for each 
\begin_inset Formula $i\geq0$
\end_inset

.
\end_layout

\begin_layout Section
State Minimization
\end_layout

\begin_layout Standard
In language 
\begin_inset Formula $L\subseteq\Sigma^{*}$
\end_inset

, string 
\begin_inset Formula $x,y\in\Sigma^{*}$
\end_inset

.
 
\begin_inset Formula $x$
\end_inset

 and 
\begin_inset Formula $y$
\end_inset

 are 
\emph on
equivalent with respect to 
\begin_inset Formula $L$
\end_inset


\emph default
, denoted 
\begin_inset Formula $x\approx_{L}y$
\end_inset

, if for all 
\begin_inset Formula $z\in\Sigma^{*}$
\end_inset

, the following is true: 
\begin_inset Formula $xz\in L$
\end_inset

 if and only if 
\begin_inset Formula $yz\in L$
\end_inset

.
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $M$
\end_inset

 be a DFA, the two strings 
\begin_inset Formula $x,y\in\Sigma^{*}$
\end_inset

 are 
\emph on
equivalent with respect to 
\begin_inset Formula $M$
\end_inset


\emph default
, denoted 
\begin_inset Formula $x\sim_{M}y$
\end_inset

, if they both drive 
\begin_inset Formula $M$
\end_inset

 from 
\begin_inset Formula $s$
\end_inset

 to the same state.
\end_layout

\begin_layout Standard
If 
\begin_inset Formula $x\sim_{M}y$
\end_inset

, then 
\begin_inset Formula $x\approx_{L(M)}y$
\end_inset

.
 So 
\begin_inset Formula $\sim_{M}$
\end_inset

 is a 
\series bold
refinement
\series default
 of 
\begin_inset Formula $\approx_{L(M)}$
\end_inset

.
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $L\subseteq\Sigma^{*}$
\end_inset

 be a regular language.
 Then there is a DFA with precisely as many states as there are equivalence
 classes in 
\begin_inset Formula $\approx_{L}$
\end_inset

 that accepts 
\begin_inset Formula $L$
\end_inset

.
 
\emph on
-- Can be constructively proved.
\end_layout

\begin_layout Standard
Corollary: A language L is regular if and only if 
\begin_inset Formula $\approx_{L}$
\end_inset

 has finitely many equivalence classes.
\end_layout

\begin_layout Standard
Algorithm for state minimization: continually refine the relation 
\begin_inset Formula $\equiv=\approx/\sim$
\end_inset

, initially 
\begin_inset Formula $\equiv_{0}=\{F,K-F\}$
\end_inset

.
\end_layout

\begin_layout Section
Algorithms for Finite Automata
\end_layout

\begin_layout Standard
Exponential: NFA to DFA, NFA to regex, decides whether two regex or NFA
 are equivalent.
\end_layout

\begin_layout Standard
Polynomial: regex to NFA, DFA to minimal DFA, decides whether two DFA are
 equivalent.
\end_layout

\begin_layout Standard
Two DFA are equivalent if and only if 
\emph on
their standard automata are identical
\emph default
.
\end_layout

\begin_layout Standard
If 
\begin_inset Formula $L$
\end_inset

 is a regular language, then there is an algorithm which, given 
\begin_inset Formula $w\in\Sigma^{*}$
\end_inset

, tests whether it is in 
\begin_inset Formula $L$
\end_inset

 in 
\begin_inset Formula $\mathcal{O}(|w|)$
\end_inset

 time using DFA.
 If using NFA, the time complexity should be 
\begin_inset Formula $\mathcal{O}(|K|^{2}|w|)$
\end_inset

.
\end_layout

\begin_layout Chapter
Context-Free Languages
\end_layout

\begin_layout Section
Context-Free Grammars
\end_layout

\begin_layout Standard
The concepts of 
\emph on
laguage recognizer
\emph default
 and 
\emph on
language generator
\emph default
.
\end_layout

\begin_layout Standard
A 
\series bold
context-free grammar
\series default
 
\begin_inset Formula $G=(V,\Sigma,R,S)$
\end_inset

, where 
\begin_inset Formula $V$
\end_inset

 is an alphabet, 
\begin_inset Formula $\Sigma\subseteq V$
\end_inset

 is the set of 
\emph on
terminals
\emph default
, 
\begin_inset Formula $R\subseteq(V-\Sigma)\times V^{*}$
\end_inset

 is the finite set of 
\emph on
rules
\emph default
, and 
\begin_inset Formula $S\in V-\Sigma$
\end_inset

 is the 
\emph on
start symbol
\emph default
.
\end_layout

\begin_layout Standard
Member of 
\begin_inset Formula $V-\Sigma$
\end_inset

 is called 
\emph on
nonterminals
\emph default
.
 For any 
\begin_inset Formula $A\in V-\Sigma$
\end_inset

 and 
\begin_inset Formula $u\in V^{*}$
\end_inset

, we write 
\begin_inset Formula $A\rightarrow_{G}u$
\end_inset

 whenever 
\begin_inset Formula $(A,u)\in R$
\end_inset

.
 For any strings 
\begin_inset Formula $u,v\in V^{*}$
\end_inset

, we write 
\begin_inset Formula $u\Rightarrow_{G}v$
\end_inset

 if and only if there are strings 
\begin_inset Formula $x,y\in V^{*}$
\end_inset

 and 
\begin_inset Formula $A\in V-\Sigma$
\end_inset

 such that 
\begin_inset Formula $u=xAy$
\end_inset

, 
\begin_inset Formula $v=xv'y$
\end_inset

, and 
\begin_inset Formula $A\rightarrow_{G}v'$
\end_inset

.
 The relation 
\begin_inset Formula $\Rightarrow_{G}^{*}$
\end_inset

 is the reflexive transitive closure of 
\begin_inset Formula $\Rightarrow_{G}$
\end_inset

.
 Finally, 
\begin_inset Formula $L(G)$
\end_inset

 the 
\emph on
language generated
\emph default
 by 
\begin_inset Formula $G$
\end_inset

, is 
\begin_inset Formula $\{w\in\Sigma^{*}:S\Rightarrow_{G}^{*}w\}$
\end_inset

; we also say that 
\begin_inset Formula $G$
\end_inset

 
\emph on
generates
\emph default
 each string in 
\begin_inset Formula $L(G)$
\end_inset

.
 A language 
\begin_inset Formula $L$
\end_inset

 is said to be a 
\series bold
context-free language
\series default
 if 
\begin_inset Formula $L=L(G)$
\end_inset

 for some context-free grammar 
\begin_inset Formula $G$
\end_inset

.
\end_layout

\begin_layout Standard
When the grammar to which we refer is obvious, we write 
\begin_inset Formula $A\rightarrow w$
\end_inset

 and 
\begin_inset Formula $u\Rightarrow v$
\end_inset

 instead of 
\begin_inset Formula $A\rightarrow_{G}w$
\end_inset

 and 
\begin_inset Formula $u\Rightarrow_{G}v$
\end_inset

.
\end_layout

\begin_layout Standard
We call form 
\begin_inset Formula $w_{0}\Rightarrow_{G}w_{1}\Rightarrow_{G}\cdots\Rightarrow_{G}w_{n}$
\end_inset

 a 
\emph on
derivation
\emph default
 in 
\begin_inset Formula $G$
\end_inset

 of 
\begin_inset Formula $w_{n}$
\end_inset

 from 
\begin_inset Formula $w_{0}$
\end_inset

, its 
\emph on
length
\emph default
 or 
\emph on
steps
\emph default
 is 
\begin_inset Formula $n$
\end_inset

.
\end_layout

\begin_layout Standard
All regular languages are context free.
 We can directly construct the rules of a CFG using DFA's transition function:
 
\begin_inset Formula $R=\{q\rightarrow ap:\delta(q,a)=p\}\cup\{q\rightarrow e:q\in F\}$
\end_inset

.
\end_layout

\begin_layout Section
Parse Trees
\end_layout

\begin_layout Standard
Show the derivation of a CFG in a tree, called 
\emph on
parse tree
\emph default
, which has 
\emph on
nodes
\emph default
, each node carries a 
\emph on
label
\emph default
, there are nodes called 
\emph on
root
\emph default
 and 
\emph on
leaves
\emph default
.
 By concatenating the labels of the leaves from left to right, we obtain
 the derived string of terminals, which is called the 
\emph on
yield
\emph default
 of the parse tree.
\end_layout

\begin_layout Standard
Two derivations are identical except for two consecutive steps, during which
 the same two nonterminals are replaced by the same two strings but in opposite
 orders in the two derivations.
 The derivation in which the leftmost of the two nonterminals is replaced
 first is said to precede the other, written 
\begin_inset Formula $D_{1}\prec D_{2}$
\end_inset

.
\end_layout

\begin_layout Standard
Two derivations 
\begin_inset Formula $D$
\end_inset

 and 
\begin_inset Formula $D'$
\end_inset

 are 
\emph on
similar
\emph default
 if the pair 
\begin_inset Formula $(D,D')$
\end_inset

 belongs in the reflexive, symmetric, transitive closure of 
\begin_inset Formula $\prec$
\end_inset

.
 We also have 
\emph on
leftmost derivation
\emph default
 and 
\emph on
rightmost derivation
\emph default
.
\end_layout

\begin_layout Standard
Leftmost derivation: we write 
\begin_inset Formula $x\overset{L}{\Rightarrow}y$
\end_inset

 if and only if 
\begin_inset Formula $x=wA\beta$
\end_inset

, 
\begin_inset Formula $y=w\alpha\beta$
\end_inset

, i.e.
 the leftmost nonterminal must be replaced.
\end_layout

\begin_layout Standard
Usually, we can disambiguate an ambiguous CFG, unless the language is 
\emph on
inherently ambiguous
\emph default
.
\end_layout

\begin_layout Section
Pushdown Automata
\end_layout

\begin_layout Standard
A 
\emph on
pushdown automaton
\emph default
 is a sextuple 
\begin_inset Formula $M=(K,\Sigma,\Gamma,\Delta,s,F)$
\end_inset

, where 
\begin_inset Formula $K$
\end_inset

 is a finite set of 
\emph on
states
\emph default
, 
\begin_inset Formula $\Sigma$
\end_inset

 is an alphabet (the 
\emph on
input symbols
\emph default
), 
\begin_inset Formula $\Gamma$
\end_inset

 is an alphabet (the 
\emph on
stack symbols
\emph default
), 
\begin_inset Formula $s\in K$
\end_inset

 is the 
\emph on
initial state
\emph default
, 
\begin_inset Formula $F\subseteq K$
\end_inset

 is the set of 
\emph on
final states
\emph default
, and 
\begin_inset Formula $\Delta$
\end_inset

, the 
\emph on
transition relation
\emph default
, is a finite subset of 
\begin_inset Formula $(K\times(\Sigma\cup\{e\})\times\Gamma^{*})\times(K\times\Gamma^{*})$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula $((p,a,\beta),(q,\gamma))\in\Delta$
\end_inset

, then when 
\begin_inset Formula $M$
\end_inset

 is in state 
\begin_inset Formula $p$
\end_inset

 with 
\begin_inset Formula $\beta$
\end_inset

 at the top of the stack, may read 
\begin_inset Formula $a$
\end_inset

 from input, replace 
\begin_inset Formula $\beta$
\end_inset

 by 
\begin_inset Formula $\gamma$
\end_inset

 on the top of the stack, and enter state 
\begin_inset Formula $q$
\end_inset

.
\family roman
\series medium
\shape up
\size normal
\emph off
\bar no
\strikeout off
\uuline off
\uwave off
\noun off
\color none

\backslash
vdash
\end_layout

\begin_layout Section
Pushdown Automata and Context-Free Grammars
\end_layout

\begin_layout Standard
Pushdown automaton is exactly what is needed to accept arbitrary context-free
 languages.
\end_layout

\begin_layout Standard
Construct a pushdown automaton from a context-free language.
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $M=(\{p,q\},\Sigma,V,\Delta,p,\{q\})$
\end_inset

, where 
\begin_inset Formula $\Delta$
\end_inset

 contains the following transitions: (1) 
\begin_inset Formula $((p,e,e),(q,S))$
\end_inset

, (2) 
\begin_inset Formula $((q,e,A),(q,x))$
\end_inset

 for each rule 
\begin_inset Formula $A\rightarrow x$
\end_inset

 in 
\begin_inset Formula $R$
\end_inset

, (3) 
\begin_inset Formula $((q,a,a),(q,e))$
\end_inset

 for each 
\begin_inset Formula $a\in\Sigma$
\end_inset

.
\end_layout

\begin_layout Standard
Construct a context-free language from a pushdown automaton.
\end_layout

\begin_layout Standard

\emph on
Simple
\emph default
 pushdown automaton: whenever 
\begin_inset Formula $((q,a,\beta),(p,\gamma))$
\end_inset

 is a transition of the pushdown automaton and 
\begin_inset Formula $q$
\end_inset

 is 
\emph on
not
\emph default
 the start state, then 
\begin_inset Formula $\beta\in\Gamma$
\end_inset

, and 
\begin_inset Formula $|\gamma|\leq2$
\end_inset

.
 The machine always consults its topmost stack symbol and replaces it either
 with 
\begin_inset Formula $e$
\end_inset

, or with a single stack symbol, or with two stack symbols.
 We can construct an equivalent simple pushdown automaton from any pushdown
 automaton.
 And then construct CFG.
\end_layout

\begin_layout Section
Languages that are and are not Context-Free
\end_layout

\begin_layout Standard
The context-free languages are 
\emph on
closed
\emph default
 under union, concatenation, and Kleene star.
 But not closed under intersection or complementation.
\end_layout

\begin_layout Standard
The intersection of a context-free language with a regular language is a
 context-free language.
 (The Cartesian product of state set of two automaton.)
\end_layout

\begin_layout Standard
The fanout of 
\begin_inset Formula $G$
\end_inset

, denoted 
\begin_inset Formula $\phi(G)$
\end_inset

, is the largest number of symbols on the right-hand side of any rule in
 
\begin_inset Formula $R$
\end_inset

.
\end_layout

\begin_layout Standard
Pumping theorem: Let 
\begin_inset Formula $G=(V,\Sigma,R,S)$
\end_inset

 be a context-free grammar Then any string 
\begin_inset Formula $w\in L(G)$
\end_inset

 of length greater than 
\begin_inset Formula $\phi(G)^{|V-\Sigma|}$
\end_inset

 can be rewritten as 
\begin_inset Formula $w=uvxyz$
\end_inset

 in such a way that either 
\begin_inset Formula $v$
\end_inset

 or 
\begin_inset Formula $y$
\end_inset

 is nonempty and 
\begin_inset Formula $uv^{n}xy^{n}z$
\end_inset

 is in 
\begin_inset Formula $L(G)$
\end_inset

 for every 
\begin_inset Formula $n\geq0$
\end_inset

.
\end_layout

\begin_layout Section
Algorithms for Context-Free Grammars
\end_layout

\begin_layout Standard
Polynomial algorithms: from CFG to pushdown automaton; from pushdown automaton
 to CFG; decide whether string 
\begin_inset Formula $x\in L(G)$
\end_inset

, 
\begin_inset Formula $G$
\end_inset

 is a CFG.
\end_layout

\begin_layout Standard
A context-free grammar 
\begin_inset Formula $G=(V,\Sigma,R,S)$
\end_inset

 is said to be in 
\emph on
Chomsky normal form
\emph default
 if 
\begin_inset Formula $R\subseteq(V-\Sigma)\times V^{2}$
\end_inset

.
 We can transform any CFG into Chomsky normal form in polynomial time.
 After that, we can use dynamic programming to complete the acceptor algorithm.
\end_layout

\begin_layout Section
Determinism and Parsing
\end_layout

\begin_layout Standard
Deterministic pushdown automaton: for each configuration there is at most
 one configuration that can succeed it.
 Deterministic CFG are those that are accepted by deterministic pushdown
 automata.
\end_layout

\begin_layout Standard
Formally, we call a language 
\begin_inset Formula $L\subseteq\Sigma^{*}$
\end_inset

 
\emph on
deterministic context-free
\emph default
 if 
\begin_inset Formula $L\$=L(M)$
\end_inset

 for some deterministic pushdown automaton 
\begin_inset Formula $M$
\end_inset

.
 Here 
\begin_inset Formula $\$$
\end_inset

 is a new symbol appended to each input string to mark its end.
\end_layout

\begin_layout Standard
The class of deterministic context-free language is 
\emph on
closed under complement
\emph default
.
 The class of deterministic context-free language is 
\emph on
properly contained
\emph default
 in the class of context-free languages.
\end_layout

\begin_layout Standard
Top-Down Parsing: the steps in the computation where a nonterminal is replaced
 on top of the stack correspond to the construction of a parse tree from
 the root towards the leaves.
\end_layout

\begin_layout Standard
Left factoring: 
\begin_inset Formula $F\rightarrow a\beta$
\end_inset

, 
\begin_inset Formula $F\rightarrow a\gamma$
\end_inset

 to 
\begin_inset Formula $F\rightarrow aE$
\end_inset

, 
\begin_inset Formula $E\rightarrow\beta$
\end_inset

, 
\begin_inset Formula $E\rightarrow\gamma$
\end_inset

.
\end_layout

\begin_layout Standard
Bottom-Up Parsing: carry out a leftmost derivation on the stack; attempt
 to read the input first and, on the basis of the input actually read, deduce
 what derivation it should attempt to carry out.
\end_layout

\begin_layout Standard
Bottom-up pushdown automata construction: 
\begin_inset Formula $G=(V,\Sigma,R,S)$
\end_inset

 is the grammar, 
\begin_inset Formula $M=(K,\Gamma,\Delta,p,F)$
\end_inset

 is the automata, where 
\begin_inset Formula $\mbox{}K=\{p,q\}$
\end_inset

, 
\begin_inset Formula $\Gamma=V$
\end_inset

,
\begin_inset Formula $F=\{q\}$
\end_inset

, and 
\begin_inset Formula $\Delta$
\end_inset

 contains the following: (1) 
\begin_inset Formula $((p,a,e),(p,a))$
\end_inset

 for each 
\begin_inset Formula $a\in\Sigma$
\end_inset

, (2) 
\begin_inset Formula $((p,e,\alpha^{R}),(p,A))$
\end_inset

 for each rule 
\begin_inset Formula $A\rightarrow\alpha$
\end_inset

 in 
\begin_inset Formula $R$
\end_inset

, (3) 
\begin_inset Formula $((p,e,S),(q,e))$
\end_inset

.
\end_layout

\begin_layout Chapter
Turing Machines
\end_layout

\begin_layout Section
The Definition of a Turing Machine
\end_layout

\begin_layout Standard
Unlike finite automata or pushdown autoamta, turing machine can be regarded
 as truly general models of computers.
\end_layout

\begin_layout Standard
Turing machines seem to form a 
\emph on
stable
\emph default
 and 
\emph on
maximal
\emph default
 class of computational devices, in terms of the computations they can perform.
\end_layout

\begin_layout Standard
A Turing machine is a quintuple 
\begin_inset Formula $(K,\Sigma,\delta,s,H)$
\end_inset

, where 
\begin_inset Formula $K$
\end_inset

 is a finite set of 
\emph on
states
\emph default
; 
\begin_inset Formula $\Sigma$
\end_inset

 is an alphabet, containing the 
\emph on
blank symbol
\emph default
 
\begin_inset Formula $\sqcup$
\end_inset

 and the 
\emph on
left end symbol
\emph default
 
\begin_inset Formula $\vartriangleright$
\end_inset

, but not containing the symbols 
\begin_inset Formula $\leftarrow$
\end_inset

 and 
\begin_inset Formula $\rightarrow$
\end_inset

; 
\begin_inset Formula $s\in K$
\end_inset

 is the 
\emph on
initial state
\emph default
, 
\begin_inset Formula $H\subseteq K$
\end_inset

 is the set of 
\emph on
halting states
\emph default
; 
\begin_inset Formula $\delta$
\end_inset

, the 
\emph on
transition function
\emph default
, is a function from 
\begin_inset Formula $(K-H)\times\Sigma$
\end_inset

 to 
\begin_inset Formula $K\times(\Sigma\cup\{\leftarrow,\rightarrow\})$
\end_inset

 such that (a) for all 
\begin_inset Formula $q\in K-H$
\end_inset

, if 
\begin_inset Formula $\delta(q,\vartriangleright)=(p,b)$
\end_inset

, then 
\begin_inset Formula $b=\rightarrow$
\end_inset

, (b) for all 
\begin_inset Formula $q\in K-H$
\end_inset

 and 
\begin_inset Formula $a\in\Sigma$
\end_inset

, if 
\begin_inset Formula $\delta(q,a)=(p,b)$
\end_inset

 then 
\begin_inset Formula $b\not=\vartriangleright$
\end_inset

.
\end_layout

\begin_layout Standard
A 
\emph on
configuration
\emph default
 of a Turing machine 
\begin_inset Formula $M=(K,\Sigma,\delta,s,H)$
\end_inset

 is a member of 
\begin_inset Formula $K\times\vartriangleright\Sigma^{*}\times(\Sigma^{*}(\Sigma-\{\sqcup\})\cup\{e\}).$
\end_inset

 All configurations are assumed to start with the left end symbol and never
 end with a blank, unless the blank is currently scanned.
\end_layout

\begin_layout Standard
The definition of 
\begin_inset Formula $(q_{1},w_{1}\underline{a_{1}}u_{1})\vdash_{M}(q_{2},w_{2}\underline{a_{2}}u_{2})$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula $C_{1}\vdash_{M}^{*}C_{2}$
\end_inset

 , configuration 
\begin_inset Formula $C_{1}$
\end_inset

 
\emph on
yields
\emph default
 configuration 
\begin_inset Formula $C_{2}$
\end_inset

.
 A 
\emph on
computation
\emph default
 by 
\begin_inset Formula $M$
\end_inset

 is a sequence of configurations 
\begin_inset Formula $C_{0},C_{1},\ldots,C_{n}$
\end_inset

, for some 
\begin_inset Formula $n\geq0$
\end_inset

 such that 
\begin_inset Formula $C_{0}\vdash_{M}C_{1}\vdash_{M}C_{2}\vdash_{M}\cdots\vdash_{M}C_{n}$
\end_inset

.
 This computation is of 
\emph on
length
\emph default
 
\begin_inset Formula $n$
\end_inset

 or it has 
\begin_inset Formula $n$
\end_inset

 
\emph on
steps
\emph default
, and we write 
\begin_inset Formula $C_{0}\vdash_{M}^{n}C_{n}$
\end_inset

.
\end_layout

\begin_layout Standard
Use a 
\emph on
hierarchical
\emph default
 notation, more and more complex machines are built from simpler materials.
\end_layout

\begin_layout Standard
The 
\emph on
basic machines
\emph default
 include the 
\emph on
symbol-writing machines
\emph default
 and the 
\emph on
head-moving machines.

\emph default
 If 
\begin_inset Formula $a\in\Sigma$
\end_inset

, the 
\emph on
a-writing machine
\emph default
 will be denoted simply as 
\emph on
a
\emph default
.
 The head-moving machines 
\emph on
L
\emph default
 and 
\emph on
R
\emph default
.
 Turing machines will ge combined in a way suggestive of the structure of
 a finite automaton.
\end_layout

\begin_layout Section
Computing with Turing Machines
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $M=(K,\Sigma,\delta,s,H)$
\end_inset

 be a Turing machine, 
\begin_inset Formula $H=\{y,n\}$
\end_inset

 consists of two halting states, denoting 
\emph on
accepting configuration
\emph default
 and 
\emph on
rejecting configuration
\emph default
.
 We say that 
\begin_inset Formula $M$
\end_inset

 
\emph on
decides
\emph default
 a language 
\begin_inset Formula $L$
\end_inset

 if for any string 
\begin_inset Formula $w$
\end_inset

, 
\begin_inset Formula $w\in L$
\end_inset

 then 
\begin_inset Formula $M$
\end_inset

 accepts 
\begin_inset Formula $w$
\end_inset

; and if 
\begin_inset Formula $w\notin L$
\end_inset

 then 
\begin_inset Formula $M$
\end_inset

 rejects 
\begin_inset Formula $w$
\end_inset

.
 We call a language 
\emph on
recursive
\emph default
 if there is a Turing machine that decides it.
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $M=(K,\Sigma,\delta,s,H)$
\end_inset

 be a Turing machine.
 Suppose 
\begin_inset Formula $M$
\end_inset

 halts on input 
\begin_inset Formula $w$
\end_inset

, and that 
\begin_inset Formula $(s,\vartriangleright\underline{\sqcup}w)\vdash_{M}^{*}(s,\vartriangleright\underline{\sqcup}y)$
\end_inset

 for some 
\begin_inset Formula $y$
\end_inset

.
 Then 
\begin_inset Formula $y$
\end_inset

 is called the 
\emph on
output of
\emph default
 
\begin_inset Formula $M$
\end_inset

 
\emph on
on input
\emph default
 
\begin_inset Formula $w$
\end_inset

, and is denoted 
\begin_inset Formula $M(w)$
\end_inset

.
 Notic that 
\begin_inset Formula $M(w)$
\end_inset

 is defined 
\emph on
only if
\emph default
 
\begin_inset Formula $M$
\end_inset

 
\emph on
halts on input 
\begin_inset Formula $w$
\end_inset

.
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $f$
\end_inset

 be any function from 
\begin_inset Formula $\Sigma_{0}^{*}$
\end_inset

 to 
\begin_inset Formula $\Sigma_{0}^{*}$
\end_inset

.
 We say that 
\begin_inset Formula $M$
\end_inset


\emph on
 computes 
\emph default
function 
\begin_inset Formula $f$
\end_inset

 if, for all 
\begin_inset Formula $w\in\Sigma_{0}^{*}$
\end_inset

, 
\begin_inset Formula $M(w)=f(w)$
\end_inset

.
 A function is called 
\emph on
recursive
\emph default
, if there is a Turing machine 
\begin_inset Formula $M$
\end_inset

 that computes 
\begin_inset Formula $f$
\end_inset

.
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $M=(K,\Sigma,\delta,s,H)$
\end_inset

 be a Turing machine, and let 
\begin_inset Formula $L\subseteq\Sigma_{0}^{*}$
\end_inset

 be a language.
 We say that 
\begin_inset Formula $M$
\end_inset

 
\emph on
semidecides
\emph default
 
\begin_inset Formula $L$
\end_inset

 if for any string 
\begin_inset Formula $w\in\Sigma_{0}^{*}$
\end_inset

 the following is true: 
\begin_inset Formula $w\in L$
\end_inset

 if and only if 
\begin_inset Formula $M$
\end_inset

 halts on input 
\begin_inset Formula $w$
\end_inset

.
 A language 
\begin_inset Formula $L$
\end_inset

 is 
\emph on
recursively enumerable
\emph default
 if and only if there is a Turing machine 
\begin_inset Formula $M$
\end_inset

 that semidecides 
\begin_inset Formula $L$
\end_inset

.
\end_layout

\begin_layout Standard
If a language is recursive, then it is recursively enumerable.
\end_layout

\begin_layout Standard
If 
\begin_inset Formula $L$
\end_inset

 is a recursive language, then its complement 
\begin_inset Formula $\overline{L}$
\end_inset

 is also recursive.
\end_layout

\begin_layout Section
Extensions of the Turing Machine
\end_layout

\begin_layout Standard
The additional features in Turing Machines do not add to the classes of
 computable functions or decidable languages, since each instance can be
 
\emph on
simulated
\emph default
 by the staandard model.
\end_layout

\begin_layout Standard
\begin_inset Formula $k$
\end_inset

-tape Turing machine are capable of quite complex computatioinal tasks.
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $M=(K,\Sigma,\delta,s,H)$
\end_inset

 be a 
\begin_inset Formula $k$
\end_inset

-tape Turing machine for some 
\begin_inset Formula $k\geq1$
\end_inset

.
 Then there is a standard Turing machine 
\begin_inset Formula $M'=(K',\Sigma',\delta',s',H)$
\end_inset

, where 
\begin_inset Formula $\Sigma\subseteq\Sigma'$
\end_inset

, and such that the following holds: For any input string 
\begin_inset Formula $x\in\Sigma^{*}$
\end_inset

, 
\begin_inset Formula $M$
\end_inset

 on input 
\begin_inset Formula $x$
\end_inset

 halts with output 
\begin_inset Formula $y$
\end_inset

 on the first tape if and only if 
\begin_inset Formula $M'$
\end_inset

 on input 
\begin_inset Formula $x$
\end_inset

 halts at the same halting state, and with the same output y on its tape.
 Furthermore, if 
\begin_inset Formula $M$
\end_inset

 halts on input 
\begin_inset Formula $x$
\end_inset

 after 
\begin_inset Formula $t$
\end_inset

 steps, then 
\begin_inset Formula $M'$
\end_inset

 halts on input 
\begin_inset Formula $x$
\end_inset

 after a number of steps which is 
\begin_inset Formula $\mathcal{O}(t\cdot(|x|+t))$
\end_inset

.
\end_layout

\begin_layout Standard
A two-way infinite tape can be easily simulated by a 2-tape machine.
\end_layout

\begin_layout Standard
A Turing machine with one tape and several heads or with two-dimensional
 tape can be simulated too.
\end_layout

\begin_layout Standard
Any function that is computed or language that is decided or semidecided
 by Turing machine with several tapes, heads, two-way infinite tapes, or
 multi-dimensional tapes, is also computed, decided, or semidecided, respectivel
y, by a standard Turing machine.
\end_layout

\begin_layout Section
Random Access Turing Machines
\end_layout

\begin_layout Standard
A 
\emph on
random access Turing machine
\emph default
 has a fixed number of 
\emph on
registers
\emph default
 and a one-way infinite tape; each register and each tape square is capable
 of containing an arbitrary natural number.
 The program of a random access Turing machine is a sequence of 
\emph on
instructions
\emph default
.
\end_layout

\begin_layout Standard
A random access Turing machine is a pair 
\begin_inset Formula $M=(k,\Pi)$
\end_inset

, where 
\begin_inset Formula $k>0$
\end_inset

 is the number of registers, and 
\begin_inset Formula $\Pi=(\pi_{1},\pi_{2},\ldots,\pi_{p})$
\end_inset

, the program is a finite sequence of instructions.
 A configuration of a random access machine 
\begin_inset Formula $(k,\Pi)$
\end_inset

 is a 
\begin_inset Formula $k+2$
\end_inset

-tuple 
\begin_inset Formula $(\kappa,R_{0},R_{1},\ldots,R_{k-1},T)$
\end_inset

, where 
\begin_inset Formula $\kappa\in\mathrm{N}$
\end_inset

 is the program counter, 
\begin_inset Formula $R_{j}\in\mathrm{N}$
\end_inset

 is the current value of Register 
\begin_inset Formula $j$
\end_inset

.
 
\begin_inset Formula $T$
\end_inset

 is the tape contents.
\end_layout

\begin_layout Standard
Any language decided or semidecided by a random access Turing machine, and
 any function computable by a random access Turing machine, can be decided,
 semidecided, and computed, respectively, by a standard Turing machine.
\end_layout

\begin_layout Section
Nondeterministic Turing Machines
\end_layout

\begin_layout Standard
A 
\emph on
nondeterministic Turing machine
\emph default
 is a quintuple 
\begin_inset Formula $(K,\Sigma,\Delta,s,H)$
\end_inset

, where 
\begin_inset Formula $K$
\end_inset

, 
\begin_inset Formula $\Sigma$
\end_inset

, 
\begin_inset Formula $s$
\end_inset

, and 
\begin_inset Formula $H$
\end_inset

 are as for standard Turing machines, and 
\begin_inset Formula $\Delta$
\end_inset

 is a subset of 
\begin_inset Formula $((K-H)\times\Sigma)\times(K\times(\Sigma\cup\{\leftarrow,\rightarrow\}))$
\end_inset

, rather than a function.
\end_layout

\begin_layout Standard
If a nondeterministic Turing machine 
\begin_inset Formula $M$
\end_inset

 semidecides or decides a language, or computes a function, then there is
 a standard Turing machine 
\begin_inset Formula $M'$
\end_inset

 semideciding or deciding the same language, or computing the same function.
\end_layout

\begin_layout Section
Grammars
\end_layout

\begin_layout Standard
A 
\emph on
grammar
\emph default
 (or 
\emph on
unrestricted grammar
\emph default
, or a 
\emph on
rewriting system
\emph default
) is a quadruple 
\begin_inset Formula $G=(V,\Sigma,R,S)$
\end_inset

, where 
\begin_inset Formula $V$
\end_inset

 is an alphabet; 
\begin_inset Formula $\Sigma\subseteq V$
\end_inset

 is the set of terminal symbols, and 
\begin_inset Formula $V-\Sigma$
\end_inset

 is called the set of nonterminal symbols; 
\begin_inset Formula $S\in V-\Sigma$
\end_inset

 is the start symbol; and 
\begin_inset Formula $R$
\end_inset

, the set of rules, is a finite subset of 
\begin_inset Formula $(V^{*}(V-\Sigma)V^{*})\times V^{*}$
\end_inset

.
\end_layout

\begin_layout Standard
A language is generated by a grammar if and only if it is recursively enumerable.
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $G$
\end_inset

 be a grammar, and let 
\begin_inset Formula $f:\Sigma^{*}\mapsto\Sigma^{*}$
\end_inset

 be a function.
 We say that G 
\emph on
computes
\emph default
 
\begin_inset Formula $f$
\end_inset

 if, for all 
\begin_inset Formula $w,v\in\Sigma^{*}$
\end_inset

, the following is true: 
\begin_inset Formula $SwS\Rightarrow_{G}^{*}v$
\end_inset

 if and only if 
\begin_inset Formula $v=f(w)$
\end_inset

.
 The function is called 
\emph on
grammatically computable
\emph default
, which is in turn 
\emph on
recursive
\emph default
.
\end_layout

\begin_layout Section
Numerical Functions
\end_layout

\begin_layout Standard
Define 
\emph on
zero, id
\emph default
, 
\emph on
succ, 
\emph default
they're primative recursive functions
\end_layout

\begin_layout Standard
plus(
\begin_inset Formula $m$
\end_inset

, 
\begin_inset Formula $0$
\end_inset

) = 
\begin_inset Formula $m$
\end_inset

, plus(
\begin_inset Formula $m$
\end_inset

, 
\begin_inset Formula $n+1$
\end_inset

) = succ(plus(
\begin_inset Formula $m$
\end_inset

, 
\begin_inset Formula $n$
\end_inset

)); mult(
\begin_inset Formula $m$
\end_inset

, 
\begin_inset Formula $0$
\end_inset

) = zero(
\begin_inset Formula $m$
\end_inset

), mult(
\begin_inset Formula $m$
\end_inset

, 
\begin_inset Formula $n+1$
\end_inset

) = plus(
\begin_inset Formula $m$
\end_inset

, mult(
\begin_inset Formula $m$
\end_inset

, 
\begin_inset Formula $n$
\end_inset

)); exp, pred, substraction...
\end_layout

\begin_layout Standard
Primitive recursive predicate: iszero.
 Then greater-than, etc...
\end_layout

\begin_layout Standard
Then we have function defined by cases: div, rem, 
\end_layout

\begin_layout Standard
The set of primitive recursive functions is 
\emph on
enumerable
\emph default
.
 We can use diagonalization argument to construct a function which is computable
 but not primitive recursive.
\end_layout

\begin_layout Standard
Call a function 
\begin_inset Formula $\mu$
\end_inset

-recursive if it can be obtained from the basic functions by the operations
 of composition, recursive definition, and 
\emph on
minimalization of minimalizable functions
\emph default
, which is in turn 
\emph on
recursive
\emph default
.
\end_layout

\begin_layout Chapter
Undecidability
\end_layout

\begin_layout Section
The Church-Turing Thesis
\end_layout

\begin_layout Standard
The Church-Turing thesis: algorithm can be rendered as Turing machine that
 is guaranteed to halt on all inputs, and all such maachines will be called
 algorithms.
\end_layout

\begin_layout Section
Universal Turing Machines
\end_layout

\begin_layout Standard
We can define a language whose strings are all legal representations of
 Turing machines.
\end_layout

\begin_layout Standard
The 
\emph on
universal Turing machine
\emph default
 
\begin_inset Formula $U$
\end_inset

 uses the encodings of other machines as programs to direct its operation.
 It takes two aguments, a discription of the machine 
\begin_inset Formula $M$
\end_inset

 and a description of an input string 
\begin_inset Formula $w$
\end_inset

.
\end_layout

\begin_layout Section
The Halting Problem
\end_layout

\begin_layout Standard
If there is a program can determine whether a program on given input halt
 
\begin_inset Formula $halt(P,X)$
\end_inset

.
\end_layout

\begin_layout Standard
Then consider a 
\begin_inset Formula $diagonal(X)$
\end_inset

 it halts if and only if not 
\begin_inset Formula $halt(X,X)$
\end_inset

.
 Then 
\begin_inset Formula $diagonal(diagonal)$
\end_inset

 halts if and only if not 
\begin_inset Formula $halt(diagonal,diagonal)$
\end_inset

.
 Contradiction.
\end_layout

\begin_layout Standard
Language 
\begin_inset Formula 
\[
H=\{"M""w":\mathrm{\text{ Turing machine }}M\text{ halts on input string}w\}
\]

\end_inset


\end_layout

\begin_layout Standard
is not recursive, but is recursively enumerable (universal Turing machine
 semidecides it).
\end_layout

\begin_layout Standard
If and only if 
\begin_inset Formula $H$
\end_inset

 is recursive, then every recursively enumerable language is recursive.
 But since the halting problem is undecidable, it's not recursive.
\end_layout

\begin_layout Standard
Therefore, the class of recursive languages is a strict subset of the class
 of recursively enumerable languages.
\end_layout

\begin_layout Standard
The class of recursively enumerable language is not closed under complement.
\end_layout

\begin_layout Section
Undecidable Problems About Turing Machines
\end_layout

\begin_layout Standard
There is no algorithm that decides, for an arbitrary given Turing machine
 
\begin_inset Formula $M$
\end_inset

 and input string 
\begin_inset Formula $w$
\end_inset

, whether or not 
\begin_inset Formula $M$
\end_inset

 accepts 
\begin_inset Formula $w$
\end_inset

.
\end_layout

\begin_layout Standard
Problems for which no algorithms exist are called 
\emph on
undecidable
\emph default
 or 
\emph on
unsolvable
\emph default
, e.g.
 the halting problem for Turing machines.
\end_layout

\begin_layout Standard
A reduction from language 
\begin_inset Formula $L_{1}$
\end_inset

 to 
\begin_inset Formula $L_{2}$
\end_inset

 i a recursive function 
\begin_inset Formula $r$
\end_inset

 such that 
\begin_inset Formula $x\in L_{1}$
\end_inset

if and only if 
\begin_inset Formula $r(x)\in L_{2}$
\end_inset

.
\end_layout

\begin_layout Standard
To show a languag 
\begin_inset Formula $L_{2}$
\end_inset

 is not recursive, we must identify a language 
\begin_inset Formula $L_{1}$
\end_inset

 which is known to be not recursive, and then reduce 
\begin_inset Formula $L_{1}$
\end_inset

 ot 
\begin_inset Formula $L_{2}$
\end_inset

.
\end_layout

\begin_layout Section
Unsolvable Problems About Grammars
\end_layout

\begin_layout Standard
Lots of problems related to grammars are undecidable.
\end_layout

\begin_layout Standard
Surprisingly, lots of problems related to context-free grammar are also
 undecidable: (a) given a context-free grammar 
\begin_inset Formula $G$
\end_inset

, is 
\begin_inset Formula $L(G)=\Sigma^{*}$
\end_inset

? (b) given two context-free grammar 
\begin_inset Formula $G_{1}$
\end_inset

 and 
\begin_inset Formula $G_{2}$
\end_inset

, is 
\begin_inset Formula $L(G_{1})=L(G_{2})$
\end_inset

? (c) given two pushdown automata 
\begin_inset Formula $M_{1}$
\end_inset

 and 
\begin_inset Formula $M_{2}$
\end_inset

, do they accept precisely the same language? (d) given a pushdown automaton
 
\begin_inset Formula $M$
\end_inset

, find an equivalent pushdown automaton with as few states as possible.
\end_layout

\begin_layout Section
An Unsolvable Tiling Problem
\end_layout

\begin_layout Standard
A 
\emph on
tiling system
\emph default
 is a quadruple 
\begin_inset Formula $\mathcal{D}=(D,d_{0},H,V)$
\end_inset

, where 
\begin_inset Formula $D$
\end_inset

 is a finite set of tiles, 
\begin_inset Formula $d_{0}\in D$
\end_inset

, and 
\begin_inset Formula $H$
\end_inset

, 
\begin_inset Formula $V\subseteq D\times D$
\end_inset

.
 A 
\emph on
tiling
\emph default
 by 
\begin_inset Formula $\mathcal{D}$
\end_inset

 is a function 
\begin_inset Formula $f\,:\,\mathrm{N}\times\mathrm{N}\mapsto D$
\end_inset

 such that the following hold: 
\begin_inset Formula $f(0,0)=d_{0},(f(m,n),f(m+1,n))\in H,(f(m,n),f(m,n+1))\in V$
\end_inset

.
\end_layout

\begin_layout Standard
The problem of determining, given a tiling system, whether there is a tiling
 by that system is undecidable.
\end_layout

\begin_layout Section
Properties of Recursive Languages
\end_layout

\begin_layout Standard
A language is recursive if and only if both it and its complement are recursivel
y enumerable.
\end_layout

\begin_layout Standard
A language is 
\emph on
Turing-enumerable
\emph default
 if and only if there is a Turing machine that enumerates it, if and only
 if is recursively enumerable.
\end_layout

\begin_layout Standard
A language is recursive if and only if it is lexicographically Turing-enumerable.
\end_layout

\begin_layout Standard
Suppose that 
\begin_inset Formula $\mathcal{C}$
\end_inset

 is a proper, nonempty subset of the class of all recursively enumerable
 lanugages.
 Then the following problem is undecidable: Given a Turing machine 
\begin_inset Formula $M$
\end_inset

, is 
\begin_inset Formula $L(M)\in\mathcal{C}$
\end_inset

?
\end_layout

\begin_layout Chapter
Computational Complexity
\end_layout

\begin_layout Section
The Class 
\begin_inset Formula $\mathcal{P}$
\end_inset


\end_layout

\begin_layout Standard
A Turing machine 
\begin_inset Formula $M$
\end_inset

 is said to be 
\emph on
polynomially bounded
\emph default
 if there is a polynomial 
\begin_inset Formula $p(n)$
\end_inset

 such that the machine always halts after at most 
\begin_inset Formula $p(n)$
\end_inset

 steps, where 
\begin_inset Formula $n$
\end_inset

 is the length of the input.
 The corresponding language is called polymonially decidable.
 The class of all polynomially decidable languages is denoted 
\begin_inset Formula $\mathcal{P}$
\end_inset

.
\end_layout

\begin_layout Standard
\begin_inset Formula $\mathcal{P}$
\end_inset

 is closed under complement.
\end_layout

\begin_layout Section
Problems, Problems...
\end_layout

\begin_layout Standard
Reachability problem.
 Euler cycle.
 Hamilton Cycle.
\end_layout

\begin_layout Standard
Optimization problems: Traveling salesman problem.
 Independent set.
 Clique.
 Node covers (use vertex to cover all edges).
\end_layout

\begin_layout Standard
Integer partitions: Partition (to two sets).
 Unary partition.
\end_layout

\begin_layout Standard
Equvalence of Finite Automata: Equivalence of deterministic finite automata
 (In 
\begin_inset Formula $\mathcal{P}$
\end_inset

).
 Equivalence of nondeteministic finite automata; Equivalence of regular
 expressions (not sure if in 
\begin_inset Formula $\mathcal{P}$
\end_inset

).
\end_layout

\begin_layout Section
Boolean Satisfiability
\end_layout

\begin_layout Standard
Problem Satisfiability: Given a Boolean formula 
\begin_inset Formula $F$
\end_inset

 in conjunctive normal form, is it satisfiable?
\end_layout

\begin_layout Standard
2-Satisfiability is in 
\begin_inset Formula $\mathcal{P}$
\end_inset

.
\end_layout

\begin_layout Section
The Class 
\begin_inset Formula $\mathcal{NP}$
\end_inset


\end_layout

\begin_layout Standard
A nondeterministic Turing machine 
\begin_inset Formula $M$
\end_inset

 is said to be 
\emph on
polynomially bounded
\emph default
 if there is a polymonial 
\begin_inset Formula $p(n)$
\end_inset

 ...
 that is, no computtion of thsis machine continues for more than polynomially
 many steps.
 Define 
\begin_inset Formula $\mathcal{NP}$
\end_inset

 to be the class of all languages that are decided by a polynomially bounded
 nondeterministic Turing machine.
\end_layout

\begin_layout Standard
Satisfiability, traveling salesman problem, are in 
\begin_inset Formula $\mathcal{NP}$
\end_inset

.
\end_layout

\begin_layout Standard
It is immediate that 
\begin_inset Formula $\mathcal{P}\subseteq\mathcal{NP}$
\end_inset

 (the analog of the fact that every recursive language is recursively enumerable
).
\end_layout

\begin_layout Standard
Is 
\begin_inset Formula $\mathcal{P}$
\end_inset

 equal to 
\begin_inset Formula $\mathcal{NP}$
\end_inset

? We're not sure.
\end_layout

\begin_layout Standard
A Turing machine 
\begin_inset Formula $M$
\end_inset

 is said to be 
\emph on
exonentially bounded
\emph default
 if ...
 The class 
\begin_inset Formula $\mathcal{\varepsilon XP}$
\end_inset

.
 
\begin_inset Formula $\mathcal{NP}\subseteq\mathcal{\varepsilon XP}$
\end_inset

.
\end_layout

\begin_layout Standard
Language be 
\emph on
polynomially balanced
\emph default
 and 
\begin_inset Formula $\mathcal{NP}$
\end_inset

 languages.
 -- Succinct certificates.
\end_layout

\begin_layout Chapter
NP-Completeness
\end_layout

\begin_layout Section
Polynomial-Time Reductions
\end_layout

\begin_layout Standard
The definition of 
\emph on
polynomial-time computable, polynomial reduction
\emph default
.
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $L_{1},L_{2}\subseteq\Sigma^{*}$
\end_inset

 be languages.
 A polynomial-time computable function 
\begin_inset Formula $\tau:\Sigma^{*}\mapsto\Sigma^{*}$
\end_inset

 is called a 
\emph on
polynomial reduction from
\emph default
 
\begin_inset Formula $L_{1}$
\end_inset

 
\emph on
to
\emph default
 
\begin_inset Formula $L_{2}$
\end_inset

 if for each 
\begin_inset Formula $x\in\Sigma^{*}$
\end_inset

 the following holds: 
\begin_inset Formula $x\in L_{1}$
\end_inset

 if and only if 
\begin_inset Formula $\tau(x)\in L_{2}$
\end_inset

.
\end_layout

\begin_layout Standard
Reduction from Hamilton Cycle to Satisfiability.
\end_layout

\begin_layout Standard
Six reductions: Partition, Knapsack, Two-Machine Scheduling.
\end_layout

\begin_layout Standard
If 
\begin_inset Formula $\tau_{1}$
\end_inset

 is a polynomial reduction from 
\begin_inset Formula $L_{1}$
\end_inset

 to 
\begin_inset Formula $L_{2}$
\end_inset

, 
\begin_inset Formula $\tau_{2}$
\end_inset

 is a polynomial reduction from 
\begin_inset Formula $L_{2}$
\end_inset

 to 
\begin_inset Formula $L_{3}$
\end_inset

, then 
\begin_inset Formula $r_{1}\circ r_{2}$
\end_inset

 is a polynomial reduction from 
\begin_inset Formula $L_{1}$
\end_inset

 to 
\begin_inset Formula $L_{3}$
\end_inset

.
\end_layout

\begin_layout Standard
A language
\begin_inset Formula $L$
\end_inset

 is called 
\emph on

\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete
\emph default
 if (a) 
\begin_inset Formula $L\in\mathcal{NP}$
\end_inset

; and (b) for every language 
\begin_inset Formula $L'\in\mathcal{NP}$
\end_inset

, there is a polynomial reduction from 
\begin_inset Formula $L'$
\end_inset

 to 
\begin_inset Formula $L$
\end_inset

.
\end_layout

\begin_layout Standard
Let 
\begin_inset Formula $L$
\end_inset

 be an 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete language.
 Then 
\begin_inset Formula $\mathcal{P}=\mathcal{NP}$
\end_inset

 if and only if 
\begin_inset Formula $L\in\mathcal{P}$
\end_inset

.
\end_layout

\begin_layout Section
Cook's Theorem
\end_layout

\begin_layout Standard
Bounded Tiling problem: Given a tiling system 
\begin_inset Formula $\mathcal{D}$
\end_inset

, an integer 
\begin_inset Formula $s$
\end_inset

, and a function 
\begin_inset Formula $f_{0}:\{0,\ldots,s-1\}\mapsto D$
\end_inset

, represented by its sequence of values 
\begin_inset Formula $(f_{0}(0),\ldots,f_{0}(s-1))$
\end_inset

, is there an 
\begin_inset Formula $s\times s$
\end_inset

 tiling by 
\begin_inset Formula $\mathcal{D}$
\end_inset

 extending 
\begin_inset Formula $f_{0}$
\end_inset

.
\end_layout

\begin_layout Standard
Bounded TIling is 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete.
\end_layout

\begin_layout Standard
Its certificate is polynomial, hence in 
\begin_inset Formula $\mathcal{NP}$
\end_inset

.
 Then encoding nondeterministic Turing machine into tiling system.
\end_layout

\begin_layout Standard
Cook's Theorem: Satisfiability is 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete.
 We can reduce Bounded Tiling to Satisfiability.
\end_layout

\begin_layout Standard
3-Satisfiability is 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete.
\end_layout

\begin_layout Standard
Max Sat is a 
\emph on
generalization
\emph default
 of Satisfiability, hence 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete.
\end_layout

\begin_layout Section
More 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-Complete Problems
\end_layout

\begin_layout Standard
We can reduce our known 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete problems to other problems, and those to still others.
\end_layout

\begin_layout Standard
Exact Cover is 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete, reduced from Satisfiability.
\end_layout

\begin_layout Standard
Hamilton Cycle is 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete, reduced from Exact Cover.
\end_layout

\begin_layout Standard
Undireced Hamilton Cycle is 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete, reduced from Hamilton Cycle.
\end_layout

\begin_layout Standard
The Traveling Salesman Problem is 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete, reduced from Undirected Hamilton Cycle.
\end_layout

\begin_layout Standard
Knapsack is 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete, reduced from Exact Cover.
\end_layout

\begin_layout Standard
Partition and Two-Machine Scheduling are 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete, reduced from Knapsack.
\end_layout

\begin_layout Standard
Independent Set is 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete, reduced from 3-Satisfiability.
\end_layout

\begin_layout Standard
Clique and Node Cover are 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete, reduced from Independent Set.
\end_layout

\begin_layout Standard
Inequivlence of Regular Expressions.
 Since the certificate doesn't have the 
\emph on
polynomial succinctness
\emph default
 property, it's not in 
\begin_inset Formula $\mathcal{NP}$
\end_inset

.
\end_layout

\begin_layout Standard
Inequivalence of *-Free Regular Expresions is 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-complete, reduced from Satisfiability.
\end_layout

\begin_layout Standard
Corollary: Unless 
\begin_inset Formula $\mathcal{P}=\mathcal{NP}$
\end_inset

, there is no algorithm which, given a regular expression or a nondeterministic
 finite automaton, constructs the minimum-state equivalent deterministic
 finite automaton in time that is polynomial in the input and the output.
\end_layout

\begin_layout Section
Coping with 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-Completeness
\end_layout

\begin_layout Standard
We can solve some special cases of 
\begin_inset Formula $\mathcal{NP}$
\end_inset

-completeness problems, such as 2-Satisfiability or when the graph is a
 tree.
\end_layout

\begin_layout Standard
Approximation algorithms can produce solutions 
\emph on
guaranteed to be close to the optimum
\emph default
.
\end_layout

\begin_layout Standard
Fully approximable problems, in that there is an 
\begin_inset Formula $\epsilon$
\end_inset

-approximation algorithm.
 Partly approximable problems, for some range of 
\begin_inset Formula $\epsilon$
\end_inset

's, but the range does not reach down to zero.
 Inapproximable problems, no 
\begin_inset Formula $\epsilon$
\end_inset

-approximation algorithm.
\end_layout

\begin_layout Standard
Backtracking and Branch-and-Bound.
\end_layout

\begin_layout Standard
Local improvement.
\end_layout

\end_body
\end_document