Automata 的一些概念

1.  pumping lemma 只能證明語言 不是 context-free



2. 可以寫出context-free grammar的語言是context-free的


3. Pumping lemma
   

   Let L be a regular language. Then there exist a const n such for every string
   w in L such that |w| ≧ n, we can break w into three string, w = xyz,
   such that :
   1.  y≠ε
   2.  |xy| ≦ n
   3.  For all k ≧ 0, the string xy^kz is also in L
   
   L = {a^nb^n | n ≧ 1}
   
   w = a^nb^n
     = xyz
   x = a^i
   y = a^j
   z = a^(n-i-j)b^n          (i+j) ≦ n and j ﹥0
   
   k = 0,
   xy^kz = xy^0z
         = xz
         = a^ia^(n-i-j)b^n
         = a^(n-j)b^n
   
   j ≧ 1, (n-j)≠n => xy^0z is not in L




4.  A  context-free  grammar  is  said  to  be  in 

   Greibach  normal  form  if  all  productions 
   have the form A → ax where a  ∈ T and x ∈ V * .

   ex:

   S → abSb | aa

   就是給每一個不是出
   現在最左邊的  terminal  加一個 
   variable ，得到
   S → aBSB | aA 

   A → a 

   B → b 

   簡單來說 每個grammar只會product出

   (至少一個symbol)+(n個variable的形式,n>=0)

   這裡的+可以看成字串相加的運算




5. A  context-free  grammar  is  in 
   Chomsky  normal  form  if  all 
   productions  are  of  the  form  A → BC , 
   or A  → a, where A, B, C are in V, and a 
   is in T.




6. 兩個  instantaneous  description  之間轉換，
   用├ 這個符號表示。例如：
   (q1 , aw, bx)├  (q2 , w, yx)  if and only if 
   (q2 , y) ∈ δ(q1 , a, b)

   代表在狀態q2且stack被放入y

   是狀態q1,讀到a,且stack的b被抽掉,產生的production之一

7. A context-free grammar G = (V, T, S, P) 
   is  said  to  be  a  simple  grammar  or  s-
   grammar  if  all  its  productions  are  of 
   the form
   A → ax, 
     where A ∈ V, a ∈ T, x ∈ V * , and any pair 
   (A, a) occurs at most once in P.




8. Regular  grammar 的限制：箭頭左邊只能有
   一個變數、右邊也只能有一個變數、且只能全
   部在最左邊或全部在最右邊。




9.  A grammar G = (V, T, S, P) is said to be 
   context-free  if  all  productions  in  P  have 
   the form A →x, where A ∈ V and x ∈ (V ∪ T) * .



10. A language L is said to be context-free if and only if there is a context-free grammar G such that L = L(G).

    一個語言被稱為context-free,只有在寫得出他的CFG的時候

參考至：

http://www.csie.dyu.edu.tw/~spring/Teaching/98_2/Formal/index.xml