บทนำทฤษฎี Automata
Automata - มันคืออะไร?
คำว่า "Automata" มาจากคำภาษากรีก "αὐτόματα" ซึ่งแปลว่า "การแสดงด้วยตนเอง" หุ่นยนต์ (Automata ในรูปพหูพจน์) เป็นอุปกรณ์คอมพิวเตอร์ที่ขับเคลื่อนด้วยตัวเองแบบนามธรรมซึ่งเป็นไปตามลำดับการทำงานที่กำหนดไว้ล่วงหน้าโดยอัตโนมัติ
หุ่นยนต์ที่มีสถานะจำนวน จำกัด เรียกว่า a Finite Automaton (FA) หรือ Finite State Machine (FSM).
คำจำกัดความอย่างเป็นทางการของ Finite Automaton
หุ่นยนต์สามารถแสดงด้วย 5-tuple (Q, ∑, δ, q 0 , F) โดยที่ -
Q เป็นชุดของรัฐที่ จำกัด
∑ เป็นชุดสัญลักษณ์ที่ จำกัด เรียกว่า alphabet ของหุ่นยนต์
δ คือฟังก์ชันการเปลี่ยนแปลง
q0คือสถานะเริ่มต้นจากการประมวลผลอินพุตใด ๆ (q 0 ∈ Q)
F คือชุดของสถานะสุดท้าย / สถานะของ Q (F ⊆ Q)
คำศัพท์ที่เกี่ยวข้อง
ตัวอักษร
Definition - อ alphabet คือชุดสัญลักษณ์ที่ จำกัด
Example - ∑ = {a, b, c, d} คือ alphabet set โดยที่ 'a', 'b', 'c' และ 'd' อยู่ symbols.
สตริง
Definition - ก string เป็นลำดับ จำกัด ของสัญลักษณ์ที่นำมาจาก ∑
Example - 'cabcad' เป็นสตริงที่ถูกต้องในชุดตัวอักษร ∑ = {a, b, c, d}
ความยาวของสตริง
Definition- เป็นจำนวนสัญลักษณ์ที่มีอยู่ในสตริง (แสดงโดย|S|).
Examples -
ถ้า S = 'cabcad', | S | = 6
ถ้า | S | = 0 เรียกว่าไฟล์ empty string (แสดงโดย λ หรือ ε)
คลีนสตาร์
Definition - ดาวคลีน ∑*เป็นตัวดำเนินการยูนารีในชุดของสัญลักษณ์หรือสตริง ∑นั่นทำให้ชุดสตริงที่เป็นไปได้ทั้งหมดที่เป็นไปได้ไม่สิ้นสุดของความยาวที่เป็นไปได้ทั้งหมด ∑ ได้แก่ λ.
Representation- ∑ * = ∑ 0 ∪ ∑ 1 ∪ ∑ 2 ∪……. โดยที่ ∑ pคือเซตของสตริงความยาวที่เป็นไปได้ทั้งหมด p
Example - ถ้า ∑ = {a, b}, ∑ * = {λ, a, b, aa, ab, ba, bb, ……… .. }
คลีนปิด / พลัส
Definition - ชุด ∑+ คือเซตที่ไม่สิ้นสุดของสตริงที่เป็นไปได้ทั้งหมดของความยาวที่เป็นไปได้ทั้งหมดที่มากกว่า ∑ ไม่รวมλ
Representation- ∑ + = ∑ 1 ∪ ∑ 2 ∪ ∑ 3 ∪…….
∑ + = ∑ * - {λ}
Example- ถ้า ∑ = {a, b}, ∑ + = {a, b, aa, ab, ba, bb, ……… .. }
ภาษา
Definition- ภาษาเป็นส่วนย่อยของ ∑ * สำหรับตัวอักษรบางตัว ∑ สามารถ จำกัด หรือไม่มีที่สิ้นสุด
Example - หากภาษาใช้สตริงที่เป็นไปได้ทั้งหมดที่มีความยาว 2 มากกว่า ∑ = {a, b} แล้ว L = {ab, aa, ba, bb}