Please enable JavaScript.
Coggle requires JavaScript to display documents.
ออโตมาตาจํากัดเชิงกําหนด (Cont.) - Coggle Diagram
ออโตมาตาจํากัดเชิงกําหนด (Cont.)
DFA ประกอบด้วยลำดับของสมาชิก 5 ตัว
Σคือ ชุดตัวอักษร (alphabet) ของสัญลักษณ์รับเข้า
Q คือ เซตจำกัดของสถำนะ (state
q0 คือ สถำนะเริ่มต้น (initial state); q0 E Q
A คือ เซตจํากัดของสถานะสิ้นสุด (final state)
& คือ ฟังก์ชันกำรผ่ำน (transition function) ที่จะอธิบำยแต่ละสถำนะ
เขียนเเทนด้วย
Extended Transition Function
ให้ Σ = (Q, Σ, q0, A, &) เป็น DFA จะกำหนดฟังก์ชันการผ่านเขียนแทนด้วย &* (ขยายฟังก์ชั่น)
สำหรับ q ใด ๆ q E Q, &* (q, A) = q
สำหรับ y ใด ๆ y E Σ* , a ใด ๆ a E Σและ q ใด ๆ q EQ
&
(q, ya) = &(&
(q, y), a)
สำหรับการระบุว่าสตริงใดๆ จะถูกยอมรับโดย DFA นิยามให้ชัดเจนได้ดังนี้
ให้ C = (Q, M, q0, A, &) เป็น DFA
สตริง x E Σ
จะถูกยอมรับโดย Σ ถ้า &
( q0, x) E A
ถ้ำสตริงไม่ถูกยอมรับ อธิบำยได้ว่ำถูกปฏิเสธ (Rejected)
อีกนัยหนึ่งคือ L เป็นภาษาใด ๆ บน Σ, L ถูกยอมรับโดย C ก็ ต่อเมื่อ L = L(C)
ตัวอย่าง
จากชุดตัวอักษร Σ= { 0, 1} และแผนภาพการผ่านของ DFAต่อไปนี้
จงตรวจสอบว่าสตริงต่อไปนี้ถูกยอมรับโดย DFA ข้ำงต้นหรือไม่
X1 = 00000111010
X2 = 010101101
ทำการอ่านค่าทุกค่าไปเรื่อยๆค่าที่อ่าน มาสามารถจบได้ที่จุดสิ้นสุดหรือเปล่า
X 1 = 00000111010 ถูกยอมรับ
X2 = 010101101 ไม่ถูกยอมรับ
