Automata, language, and computational complexity

2018-12-24

字数统计: 1.4k字 | 阅读时长≈ 8分钟

参考课程内容 https://courses.engr.illinois.edu/cs373/sp2013/Lectures/

Closure properties of regular language & regular expression

Regex to nfa translation

Dfa minimization algorithm

Minimization of DFA - Table Filling Method (Myhill-Nerode Theorem)

Myhill-nerode theorem

Further more there is a minimized dfa having precisely one state for each equivalence class!!!
equivalence classes classification: how to tell what equivalence classes are there?
https://courses.cs.washington.edu/courses/cse322/05wi/handouts/MyhillNerode.pdf
Regular: we can use above algorithm on DFA minimization to find out each equivalence classes
Nonregular:

Pumping lemma prove nonregular language

Testing regularity finite language is regular infinite language can be tested by pumping lemma

Testing whether a language is regular or not

https://www.youtube.com/watch?v=KSczX111n3U

CFG DESIGN Regular language to CFG,

对每一个dfa的state设计一个nonterminal variable；
对于每个transition add 相应的rule （根据不同的input）
对于accepting state的nonterminal variable 让他生成空的string
This cfg generates the same language that dfa recognizes.

AMBIGUITY

A string is derived ambiguously if it has one or more left/right most derivation tree.
A Grammar G is ambiguous if it generates some string ambiguously.

Chompsky Normal Form

(CFG simplification: removal of null ε production + unit production elimination + adding auxiliary variable & rewrite)
https://www.youtube.com/watch?v=EF09zxzpVbk&list=PLBlnK6fEyqRgp46KUv4ZY69yXmpwKOIev&t=5s&index=76

For each direct null production A-> null , look for all productions whose right hand side contains A. Replace each occurrences of A in these production with null. By each occurences, it means all possible location of A that can be nullified. Finsh the resulting productions without A->null, looking for the next one for ex B->null until no null productions exist.

Or a graph-algorithm:
Create a directed cyclic graph where each vertex represent a nonterminal for all nonterminals.
Add an edge if there is a unit production.
Collapse all strongly connected components into a single vertex (meaning these nonterminal are equivalent, merge their production rules in the grammar)
Start from sink S, augment production rules of the sink to all nonterminals that go to sink, then remove the edges from all nonterminals that go to sink. Repeat this until no edges exist

CYK algorithm O(n^3)
(Dynamic Programming parsing/recognizing if a string is in the language of cfg)
Assume in put is in CNF form.

For example, to parse “id ( id , id )” 6 character sequence, we construct 6 by 6 grid with diagonals filled in all possible nonterminal that can derive the i-th symbol for i=1 to i=6.

Then we fill in each successive diagonals bottom up:
For each square, consider ALL possible ordered pair of the nonterminals one from left one from below, for each pair, if it can be derived from a rule(notice we have cnf), we put the lhs nonterminal of that rule to that squares

If the starting nonterminal appear in the upper right corner of the grid we accept the string

Non determinstic Push down automata
Equivalence of cfg and nondeterminstic pda :
A language is generated by a cfg = it is recognized by a npda
https://people.eecs.berkeley.edu/~sseshia/172/lectures/Slides8.pdf

For example.

Non context-free language:

For any context free language L, there is a pumping length p such that for any string
z ∈ L of sufficient length p≥1 or more, there is a decomposition of string z into 5−PART uvwxy s.t.:

|vwx|≤p middle three≤p (not too far apart)

|vx|>0 pumping part of length nonegative

for any i≥0 uv^i wx^i y stays in L

Both CFG-PL AND REG-PL are necessary but not sufficient conditions for context-freeness/regularity.

pumping lemma proof idea: for a sufficiently long string and its parse tree, the longest path in the tree by pigenhole principle must have nonterminals that repeat. Therefore Pumping up or down vx, it will remains a valid parse tree

Language hierarchy & Decidable and recognizable language

A decision problem can be expressed as a language, which is a set
A language is called a Recursively enumerable set (language) [also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable] if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.

Recursive set, decidable set, computable set refers to the set of decision problem that are decidable in polynomial time

A complete set is a set of problems that are “hard”:
Np hard: every problem in np can reduce to it
Ex. To prove np-complete first show it is np, then prove it is np hard, namely choose a np complete problem and reduce to it

https://en.wikipedia.org/wiki/Complete_(complexity)

Proving problems undecidable
Turing machine and halting problem
Refers to handouts

多带图灵机与单带图灵机等价
A turing machine accepts input if there is a sequence of configuration from starting config to accepting config
A turing machine is decidable if there is some decider for it(always halt and acc or rej).
Every NDTM has a equivalent DTM
ATM, HaltTM, Etm, Eqtm, PCP is undecidable but Turing-recognizable/recursively enumerable

Undecidability and Rice’s theorem
Rice’s theorem:

A property is a set of Turing machine. A TM satisfies P means TM is in the set.
A property P is nontrivial means there is a TM that satisfies it and there is a TM that does not satisfies it.
A property P is trivial means either it is satisfied by all TMs or it is satisfied by no TMs.

Any nontrivial property about the r.e. language recognized by a Turing machine is undecidable.

Reduction https://en.wikipedia.org/wiki/Reduction_(complexity)
A reduces to B means we can use an efficient solution of B as a subroutine to solve A hardness of B 大于等于 A
Computational complexity
https://blog.csdn.net/golden1314521/article/details/51470999

NP completeness theory is designed to be applied only to decision problem.
解决一个decision problem 等价于recognizing a corresponding language
A language is a set that contains all strings accepted by the turing machine.
Class P：以单带图灵机定义的【所有多项式时间内deterministically recognizable language】
Class NP: NTM Augmented Model of one tape turing machine with guessing ability
NTM 定义了 class NP: All languages recognizable nondeterministically in Polynomial time / there is a polynomial time NDTM program that accepts the language
NP is the class of languages that have polynomial time verifiers for the membership of an arbitrary instance given.

A p-time mapping reduce to B means: there is a transformation function that given an instance a of A 包装成 instance of B f(a)=b in polynomial time such that membership of a and b in A and B. resp 同进同出

多项式时间于伪多项式时间
动态规划解决subsetsum

Textbook Reference

Computers and Intractability A Guide to the Theory of NP Completeness - Michael R. Garey and David S. Johnson
Introduction to the theory of computation third edition - Michael Sipser
Introduction To Automata Theory, Languages, And Computation 3rd - John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman

打赏

版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！