• The class of languages accepted vy finite automata is closed under:
  
  1. union
  2. concatentenation
  3. Kleene star
  4. complementation
  5. intersection
• A language is regular if and only if it is accepted by finite automaton
  正则表达式和DFA， NFA的相互转化按照步骤生成
• Pumping Theory ： Let L be a regular language. There is an integer n ≥ 1 such that any string w ∈ L | w | ≥ n can be rewritten as w = x y z such that y ≠ e , | x y | ≤ n , and x y i z ∈ L for each i ≥ 0

  Give DFA or NFA write Regular Expression
  Give regular expression, write DFA or NFA
  Show a given language is (construct) or is not regular (pumping)

• context-free and pushdown自动机

  • context-free grammar
    = ( V , , S ) where
    is an alphabet
    Σ is the set of terminals , is a subset of R is the set of rules ( V − Σ ) × V ∗ is the start Symbol, is an element of V − Σ
  • all regular languages are context-free
  • parse tree, leftmost derivation, rightmost derivation
    Grammars with strings that have two or more distinct parse trees are called ambiguous

• PDA

  = ( K , , F ) where
  is a finite set of states
  Σ is an alphabet (the input symbols)
  is an alphabet (the stack symbols)
  s ∈ K is initial state
  F ⊆ K is the set of final states
  is the transition relation ( K × ( Σ ⋃ { e } ) × Γ ∗ ) × ( K × Γ ∗ )

• The class of languages accepted by PDA is exactly the class of context-free languages
  The transitions from CFL to PDA:

  ( ( p , e , e ) , ( q , S ) ) ( ( q , e , A ) , ( q , x ) ) for each rule A → x
• ( ( q , a , a ) , ( q , e ) ) for each a ∈ Σ .

• CFL are closed under union, concatenation, Kleene star, CFL在补和交上不封闭
• CFL与正则的交集为CFL
• pumping theory : Let = ( V , , S ). Then any string w ∈ L ( G ) of length greater than ϕ ( G ) | V − Σ | can be written as w = u v x y z in such a way that either or y is nonempty and u v n x y n z is in L ( G ) for every n ≥ 0

  Given context-free language, write context-free grammar and PDA
  Give context-free grammar, write PDA
  Show a given language is or is not Context-free

• Turing Machine and Recursive Enumerable Language

  • Turing machine

    = ( K , , H ) where
    is a finite set of states
    Σ is an alphabet, containing the blank symbol and the left end symbol , but not containing the symbol s ∈ K is the initial state
    H ⊆ K is the set of halting states
    , the transition function ( K − H ) × Σ K × ( Σ ⋃ { → , ← } )

  • 一些图灵机的符号表达(左右平移机( S ← , S → ), 复制机)
    

  • decide L : if w ∈ L accepts w , and if w ∉ L rejects w
    Call a language recursice if there is a TM decides it.

  • A function is called recursive if there is a TM computes f
  • semidecides L : w ∈ L halts on input w
    Call a language recursicely enumerable iif there is a TM semidecides it.
  • if a language is recursive, then it is recursively enumerable
  • the complement of recursive language is also recursive
  • 多带和复合
    Corollary : Any function that is computed or language that is decided or semidecided by a k-tape TM is also computed, decided or semidecided by a standard TM.
• Grammar
  = ( V , , S ) where
  is an alphabet
  Σ is the set of terminals , is a subset of R is the set of rules ( V ∗ ( V − Σ ) V ∗ ) × V ∗ is the start Symbol, is an element of V − Σ
• a language is generated by a grammar iif it is recursively enumerable
  递归可枚举只在补和差下不封闭
• computes f , if: S w S ⇒ ∗ G v v = f ( w ) .
  A function is called grammatically computable iif there is a grammar G computes it.
• A fucntion is recursive iif it is grammatically computable
• the transition form TM to Grammar? (P230)
  
• Numerical Function
  
  • Basic Function:
    
    1. zero, z e r o k ( n 1 , n 2 , . . . , n k ) = 0
    2. identity, i d k , j ( n 1 , n 2 , . . . , n k ) = n j
    3. successor, s u c c ( n ) = n + 1
    4. The primitive recursive functions are all basic functions, and all functions that can be obtained by them by any number of successive application of composition and recursive definition
    5. other primitive resursive funstion:
       p l u s ( m , n ) = m + n m + n m u l t ( m , n ) = m ∗ n m ∗ n e x p ( m , n ) = m n m ↑ n
    6. all constant functions of the form f ( n 1 , . . . , n k ) = 17 s g n ( n ) which is zero if n = 0 m ∼ n = m a x { m − n , 0 } (defined use a predecessor function p r e d ( 0 ) = 0 , p r e d ( n + 1 ) = n )
    7. primitive recursive predicate (primitive functions that only takes values 0 and 1):
       g r e a t e r − t h a n ( m , n ) g r e a t e r − t h a n − o r − e q u a l ( m , n ) e q u a l ( m , n ) i s z e r o ( n ) i s o n e ( n ) p o s i t i v e ( n )
    8. Those function’s negation, disjunction and conjunction are also primitive recursive predicates
    9. Funstion defined by cases:(can be written as)
       f ( n ) = p ( n ) ∗ g ( n ) + ( 1 ∼ p ( n ) ) ∗ h ( n ) r e m ( m , n ) d i v ( m , n )
• not all computable functions are primitive recursive
• denote minimalization of m [ g ( n 1 , n 2 , . . . , n k , m ) = 1 ] The obvious method:
  m : = 0 ;
  while g ( n 1 , n 2 , . . . n k , m ) ≠ 1 m : = m + 1
  output But it is not a algorithm becaues it may fail to terminate
  
  • call a function g minimalizable if the above method always terminates.
  • Call a function -recursive if it can be obtained form basic functions by operations of composition, recursive definition, and minimalization of minimalizable funtions.
  • l o g ( m , n ) = μ p [ g r e a t e r − t h a n − o r − e q u a l ( ( m + 2 ) ↑ p , n + 1 ) ]
  • A function is -recursive iif it is recursive(that is, computable by a TM)

• 若有 X ≤ Y （X规约到Y）， X 不可判定，则 Y 不可判定；Y 可判定， 则 X 可判定。

• A lanuage is recursive iif both it and its complement are recursively enumerable
• Turing-enumerable and lexicographioally Turing enumerable
  
  
  • A language is Turing-enumerable iif there is a TM enumerates it.
  • A language is recursively enumerable iif it is turing-enumerable.
    
  • A language is recursive iif it is lexicographically Turing-enumerable

来自总结的一些例子：

正则语言的子集也可能非正则。

递归与 递归等价

判断下面问题是否可判定
参考链接

• 两个基本问题(前者为递归可枚举但不递归，后者不是递归可枚举)
  
  
  1. 一个图灵机至少有481个状态 （YES）
  2. 给定图灵机在空串上走了481步还没有停机 （YES）
  3. 给定图灵机,判断它是否在一些输入上经过481步还没有停机 （YES）
  4. 给定图灵机，判断它是否在所有输入上经过481步还没有停机 （YES）
  5. 给定图灵机是否接受空串 （NO）
  6. 给定TM M, 是否存在在M上停机的串？ （NO）
     给定TM M，M是否在所有串上停机？ （NO）
  7. 给定TM M，is L(M) finite？ （NO）(通过取非？)
  8. 给定TM M， 带上是否出现过a(a )？ （NO）
  9. 给定 M 1 , M 2 ，他们是否在同一个字符串上停机？ （NO）
  10. 给定M， 只要M接受w, M接受 { M | | L ( M ) | > 2 } . 递归可枚举但不递归
      
  11. countable
      
  12. RE