2301379 Theory of Computation

• Week 5 (2/2): Regular Grammar
• Week 5 (1/2): Pumping Lemma
• Week 4 (2/2): FA Minimizing states
• Week 4 (1/2): FA RegEx
• Week 3 (2/2): NFA
• Week 3 (1/2): FA Closure using DFA
• Week 2 (2/2): FA Design
• Week 2 (1/2): Finite Automaton
• Week 1 (2/2): RegEx
• Week 1 (1/2): Introduction

Regular expressions

• John C. Martin. Introduction to Languages and the Theory of Computation. International edition, 4th edition, 2011. Chapter 3, Exercise 3.7.
• Try solving this crossword puzzle.

  The regular expressions are defined on POSIX standard. It's not easy to solve this puzzle by hand. You may write a small program to solve this problem.

• การสกัดข้อมูล event จากอีเมล

  วิธีหนึ่งในการสกัดข้อมูล event ออกมาจากอีเมลคือจับ pattern ของข้อมูลที่สำคัญเหล่านี้ให้ได้ หากให้ input เป็นหน้าเว็บเพจ เมื่อตัดเอา html tags ต่างๆออกไป และได้เฉพาะข้อความอีเมลแล้ว (ได้ plain text แล้ว) เราสามารถเขียน regular expression เพื่อ match ข้อมูลต่างๆของ event นั้นๆ

  ให้ลองคิด regular expression สำหรับสกัดข้อมูล event ภาษาไทย งานชื่ออะไร จัดที่ไหน เมื่อไหร่ ใครจัด

  เช่น ข้อความในอีเมลเป็นดังนี้

  ขอเรียนเชิญคณาจารย์ภาควิชาฯ ทุกท่าน ร่วมงานวันไหว้ครูภาควิชาฯ ประจำปีการศึกษา 2556 ในวันพฤหัสบดีที่ 6 มิถุนายน 2556 เวลา 10.00 - 12.00 น. ณ ห้อง 301 อาคารมหามกุฎ

  ควรจะได้

  • ชื่องาน: วันไหว้ครูภาควิชาฯประจำปีการศึกษา 2556
  - อาจจะตัดมาได้แค่ วันไหว้ครูภาควิชาฯ ก็ยังถือว่าอ่านรู้เรื่อง ใช้ได้อยู่
  • วัน: วันพฤหัสบดีที่ 6 มิถุนายน 2556
  - ได้มาแค่ 6 มิถุนายน 2556 ก็ได้เช่นกัน
  • เวลา: 10.00 - 12.00 น.
  • สถานที่: ห้อง 301 อาคารมหามกุฎ
  เป็นต้น
• เมื่อสักปีก่อนภาษาสก๊อยกำลังได้รับความนิยม หากลองสังเกตดู จะเห็นว่าภาษาสก๊อยคือการ "แทนที่" อักขระด้วยอักขระอื่นซึ่งออกเสียงเดียวกัน ตัดสระบางตัวซึ่งยุ่งเหยิงออก เติมการันต์ลงไปบ้าง ใช้ไม้ตรีเยอะๆ เช่น น -> ณ, ย -> ญ, อ -> ฮ เป็นต้น

  ลองเขียน substitution rules สำหรับการแปลงภาษาธรรมดาเป็นภาษาสก๊อยดู

  ข้อสังเกต

  การแปลงภาษาธรรมดาเป็นภาษาสก๊อยทำได้ไม่ยาก แต่หากต้องการแปลงกลับโดยต้องสะกดให้ถูกต้องนั้นยากกว่าหลายเท่า แต่ถ้าทำได้ การแปลงกลับนี้จะเทียบเท่าโปรแกรม spellchecker
  http://narze.github.io/toSkoy/

Problem list

Odd-numbered exercises should be submitted and presented to Ajarn Dittaya on Tuesday, 13.00-16.00.

Even-numbered exercises should be submitted and presented to Ajarn Jaruloj on Wednesday, 10.00-11.00.

Please make an appointment before you come to submit your work.

Syllabus