2301379 Theory of Computation

Refer to all slides from 2015-First semester

Regular expression

• RegEx crossword puzzle
• Solve all of the tutorial and beginner problems
• pythex: Test your regex online
• แบบฝึกหัด
  • แบบฝึกหัดการเขียน regular expression
  • แนวทางการให้คะแนน

Deterministic finite automata

• DFA simulator and configuration
• เขียนโปรแกรมจำลองการทำงานของ DFA ที่กำหนด
• ไฟล์เริ่มต้น, Test cases
• Construct a DFA
สร้าง DFA ต่างๆ ตามข้อกำหนดต่อไปนี้
• Construct DFA from description of other DFA
กำหนด $A$ และ $B$ เป็น DFA จงสร้าง
• $C$ เป็น DFA โดยที่ $L(C) = L(A) \cup L(B)$
• $C$ เป็น DFA โดยที่ $L(C) = L(A) \cap L(B)$
• $C$ เป็น DFA โดยที่ $L(C) = \{w \mid w \text{ เป็น prefix ของ } x \text{ และ } x \in L(A)\}$
• ไฟล์เริ่มต้น, ตัวอย่างเครื่อง $A$ และ $B$
• Design a DFA from language description
กำหนด $\Sigma= \{0,1\}$ และ $w \in \Sigma^*$ เป็น binary string ซึ่งแทนจำนวนเต็มบวกฐานสองและศูนย์ จงสร้าง
• $A$ เป็น DFA โดยที่ $L(A) = \{w \mid w \text{ เป็นจำนวนคู่}\}$
• $A$ เป็น DFA โดยที่ $L(A) = \{w \mid w \text{ หารด้วยสามลงตัว}\}$

Nondeterministic finite automata

• NFA simulator
• เขียนโปรแกรมจำลองการทำงานของ NFA ที่กำหนด
• ไฟล์เริ่มต้น, Test cases
• Construct an NFA from description of other NFA
กำหนด $A$ เป็น NFA จงสร้าง
• $C$ เป็น NFA โดยที่ $L(C) = \{y \mid x,y,z \in \Sigma^* \text{ และ } xyz \in L(A)\}$
• ไฟล์เริ่มต้น, Test cases

NFA, DFA, RegEx

• สร้าง DFA ที่สมมูลกับ NFA ที่กำหนด
• สร้าง RegEx จาก NFA ที่กำหนด
• โจทย์, ไฟล์เริ่มต้น, Test cases

Deterministic Turing machine

• DTM simulator and configuration
• เขียนโปรแกรมจำลองการทำงานของ DTM ที่กำหนด
• ไฟล์เริ่มต้น, ตัวอย่างเครื่อง $M_2$ ในเอกสาร, Test cases

Syllabus

First semester, 2015

First semester, 2013