Introduction
- Some math preliminaries:
- Set theory: union, intersection, difference, cartesian product, complement
- Function: 1-1 (injective) (two diff a lead to two diff f(a)), onto (subjective) (one b --> one a), bijection (both injective and subjective)
- Boolean
- how to solve problem
- many techniques: constructive (give method of creating object), nonconstructive, contradiction, induction style
- pigeon hole principle can lead to many consequences
Finite automata and regular language
-
regular language --> can be processed by computers having a small amount of memory
-
toll-gate control problem: using automata to remember which state (how many money)
-
finite automaton is 5 tuples (states, alphabet (values, for toll gate is 5,10,25), transition function, start state, accept states)
-
we have "accept states" and "reject states"
-
language L(M) accepted by M is defined by "set of all string" accepted by M
-
language A is regular, if there exist automaton M such is A = L(M)
-
NFA: state r, read symbol a -> goto uniquely defined state (r,a) http://infolab.stanford.edu/~ullman/ialc/spr10/slides/fa3.pdf
-
DFA: 0 or more than 1 possibles to goto
-
DFA has same power as NFA
-
NFA is 5 tuples too, different is in alphabet set
-
NFA recognize "formal language", compare to "regular language"
Regular expression
-
regular expression means to describe language
-
class of languages that can be decribed with regular expression, coincides with class of regular language
-
regular expression can be combined
-
L is regular language if and only if L is described by regular expressions
-
class of regular language is closed under various of operation --> it can be described under NFA or NFA and regular expression
-
we have tool to prove a lang is regular, or is not regular
-
amount of memory needed to determine or note given string is in a language or not is finite! (but only for language that have "repetitive" structure)
- pumping lemma: any sufficient long string can be "pumped", (or repeat partially)
Higman's theorem:
- subsequence definition: sequence which obtained by delete 0/more from others
- Theorem: basically, subsequence language (SUBSEQ(L)) is regular
Dickson's theorem
- dominated definition: a set which all element is <= other set (for N set only)
- Theorem: basically, a set M is dominated is finite
Context Free Language
-
context free is class of languages that have some sort of recursive structure
-
has start variable and terminal variable
-
derive rule: Take any variable in the current string and take any rule that has this variable on the left-hand side
-
is a 4 tuples, variables |
-
regular languages are context-free! (prove by construct rule by state machine) (3.3.1 theorem), this theorem prove gives a way to construct rule from state machine
-
Chomsky normal form: strict form of context free grammar, just like normalize in DB
- there exist a way to convert to normal form
-
Pushdown automata : the class of languages that can be accepted by these automata is exactly the class of context-free languages
- has stack and tape, tape head, state control
- determistic pushdown automaton
-
Equivalent of pushdown automata and context free language: nondetermistic pushdown automata and context free grammar equivalent in power
-
Turing Machine
- k tapes, divided into cells, infinite, each cell contain symbol
- deterministic turing machine is a 7-tuples
- has transition function, tell us what machine can do in "one computation step"
- using turing machine to accept palindrome
-
Equivalent computing model:
- one tape turing machine, k tape turing machines, non-deterministic turing machine, java prog, c++ prog, lisp prog
- all aboves can be converted to each other
Church turing thesis: - Every computational process that is intuitively considered to be an algorithm can be converted to a Turing machine.
Decidable and Undecidable language - A is decidable, if there exists an algorithm that (i) terminates on every input string w, and (ii) correctly tells us whether w ∈ A or w ̸∈ A.
TODO: - turing machine construction methodology