[Theory of Computation-02] Automata: The method and the madness

     เป็นการศึกษาเกี่ยวกับ เครื่องคำนวณแบบนามธรรม (Abstract Computing Devices) เนื่องจากมันเป็นนามธรรมจับต้องไม่ได้ เราจึงมาเรียน Turing Machine (TM) ซึ่งเป็น โมเดล ของคอมพิวเตอร์ที่ใช้อยู่ในปัจจุบัน แต่ก่อนที่เราจะศึกษา TM เราต้องรู้จักกับ Put Down Automata(PDA) และก่อนที่จะรู้จัก PDA เราจะต้องรู้จักกับ Finite Automata (FA)

     FA  --->  PDA  --->  TM

      ทำไมต้อง? Turing Machine
      เพราะจะได้รู้ว่าคอมพิวเตอร์นั้นทำงานอย่างไร

      คอมพิวเตอร์ปัจจุบันมีสถาปัตยกรรม แบบ Von Neumann
      เราจะมองคอมพิวเตอร์เป็น 2 มุมคือ
           1. Structural(เชิงโครงสร้าง)
           2. Functional(เชิงหน้าที่การทำงาน) - ต้นแบบของหน้าที่การทำงานของคอมพิวเตอร์ คือ Turing Machine นั่นคือ เราอยากจะรู้ว่าเครื่องคอมพิวเตอร์ทำงานอย่างไร โดยผ่าน Turing Machine

ALAN TURING, 1930 คิดเครื่อง Turing Machine นี้ขึ้นมาเพราะอยากรู้ว่า คอมพิวเตอร์มีความสามารถมากน้อยแค่ไหน (คอมพิวเตอร์มีขอบเขตความสามารถอย่างไร)

โดยการใส่ปัญหา(Problem) ต่างๆเข้าไปในตัว Turing Machine และ เจ้า Turing Machine นี้ก็พบว่า มีทั้ง

           1. ปัญหาที่แก้ได้ (Decidable Problem)
           2. ปัญหาที่แก้ไม่ได้ (Undecidable Problem)

ทั้งสองข้อนั่นคือ ความสามารถในการแก้ปัญหาเราเรียกว่า = Decidability(ความสามารถในการแก้ปัญหา)

ต่อมา COOK ได้ศึกษาต่อจาก ALAN TURING แต่เขาสนใจเพียงแค่ Decidable Problem และพบว่าปัญหาที่แก้ได้นั้นแก้ได้อย่าง

           1. แก้ได้อย่างมีประสิทธิภาพ (Tractable Problem)
           2. แก้ได้อย่างไม่มีประสิทธิภาพ (Intractable Problem)

    1.แก้ได้อย่างมีประสิทธิภาพ คือ แก้ได้อย่างทันความต้องการ มีความเร็วในการแก้ไขปัญหาหรือเวลา Execution <= Polynomial(เช่น n^2) Time
    2.แก้ได้อย่างไม่มีประสิทธิภาพ คือ แก้ได้อย่างไม่ทันความต้องการ มีความเร็วในการแก้ไขปัญหาหรือเวลา Execution > Polynomial Time (เช่น Exponential, Factorial)

         ในขณะที่ ALAN TURING ได้คิดค้นตัว Turing Machine ที่เป็นโมเดลแล้ว ก็มี CHOMSKY คิดค้นภาษาที่เหมือนกับตัว Turing Machine ภาษาดังกล่าวคือ Recusively Enumerable Language ซึ่งเป็นภาษาที่ Turing Machine สามารถทำการ Recognize ได้ หรือก็คือ ALAN TURING คิดเครื่อง ส่วน CHOMSHY คิดภาษา ทั้งภาษาและเครื่องดังกล่าวมีความ Equivalent กัน
          Context-Free Language เป็นภาษาที่ถูกรู้จำโดย PDA
          Regular Language เป็นภาษาที่ถูกรู้จำโดย FA

          ทำไมถึงต้องเรียนวิชานี้(Why study automata theory?)
          1. Software Design
          2. Lexical analysis และ Parser
          3. Search Engine
          4. Verification (การทวนสอบ) - การตรวจสอบกับ Spec ว่าตรงกันหรือไม่

1.Finite Automata (FA)

  

* ในแต่ละ State ต้องใส่ชื่อ State ด้วย

เช่น ...  สถานะการเปิด/ปิดไฟ INPUT = PUSH

== Lecture on 16/6/2554 == 1 ชั่วโมง 30 นาที ==

เรื่องที่ต้องการรู้ ปูพื้นก่อนเข้าสู่เนื้อหาวิชา

        Introduction to formal proof


     1. Deductive proof คือการพิสูจน์โดย พิสูจน์จาก เหตุไปหาผล เช่น
  
        Theorem 1.3: If x >= 4 Then 2^x > x^2 --- TRUE
        
        Theorem 1.4: if x is the sum of the square of 4 positive integers then 2^x >= x^2


        1. x = a^2 + b^2 + c^2 + d^2                           กำหนดให้
        2. a >= 1, b >= 1, c >=1, d >= 1                        กำหนดให้
        3. a^2 >= 1, b^2 >= 1, c^2 >= 1, d^2 >= 1      2, คุณสมบัติของเลขคณิต
        4. x >= 4                                                            1, 3
        5. 2^x >= x^2                                                    Thorem 1.3


        คำที่ใช้ในการพิสูจน์ if ... then
        1. H Implies C
        2. H Only If C
        3. C IF H
        4. Whenever H Holds, C follows


       การพิสูจน์แบบก็ต่อเมื่อ ( <--> )
       1. IF part                         : if B then A
       2. Only-If part                 : if A then B

       Proof about sets (พิมสูจน์ว่า 2 เซตใดเท่ากัน) 
  
       ให้ E และ F เป็นเซตใดๆ


       1. Proof that if x ∈ E Then x ∈ F
       2. Proof that if x ∈ F Then x ∈ E


       2. Contrapositive


       if H then C
       if NOT C THEN NOT H
       
      3. Contradiction
      
      if H Then C
      if H Then NOT C              -- พิสูจน์อันนี้เป็นจริง แสดงว่า ข้อความที่ให้มาเป็นเท็จ !


      4. finding counterexamples
      
      หาตัวอย่าง อย่างน้อยที่สุด 1 เพื่อแย้วกับทฤษฏี ทฤษฎีที่มี counterexample จะเรียกว่า Alleged Theorem การพิสูจน์ว่าไม่เป็นจริงเรียกว่า Disproof


      5. Inductive proof

      เราจะพิสูจน์ S(x)       


      1. พิสูจน์ Basic Step  S(ตัวที่เล็กที่สุด) เป็นจริง
      2. พิสูจน์ Inductive Step  พิสูจน์ IF S(n) Then S(n+1) เป็นจริง


      เทคนิค พยายามแยก พจน์ที่ n+1 ออกมาจาก n ***


      ตัวอย่าง
      พิสูจน์ 

      
      
        The central concept of Automata theory
      Theory 

1. Language แทนด้วยสัญลักษณ์ ∑*
2. Alphabet ∑ = {A, B, C ..., Z} Set ของ Alphabet ภาษาอังกฤษ 
3. String ที่เกิดจากการเอา Alphabet มาต่อกัน เช่น COM 

          S = String

         |S| = 0 คือ Empty String(Ɛ หรือ แรมด้า)

 
ถ้าให้ ∑ = {0, 1}


    |S| = 0 , ∑⁰  | มีสมาชิก 1 ตัว
     |S|  =  1 , ∑¹  | {0, 1}
     |S|  =  2 , ∑²  | {00, 01, 10, 11}
      .              .
      .              .
      .              .
    ∑* = ∑⁰ U ∑¹ U ∑² U ... = {Ɛ, 0, 1, 00, 01, 10, 11, 000, ...} 
     ∑*  =  ∑⁺ U {Ɛ}