{"id":1032,"date":"2023-08-15T15:05:22","date_gmt":"2023-08-15T22:05:22","guid":{"rendered":"https:\/\/labs.wsu.edu\/scads\/?page_id=1032"},"modified":"2025-07-02T12:33:09","modified_gmt":"2025-07-02T19:33:09","slug":"cpts-317-automata-and-formal-languages","status":"publish","type":"page","link":"https:\/\/labs.wsu.edu\/scads\/teaching\/cpts-317-automata-and-formal-languages\/","title":{"rendered":"CptS 317: Automata and Formal Languages"},"content":{"rendered":"\n

CptS 317: Automata and Formal Languages <\/h1>\n\n\n\n
\n\n\n\n

Course Information<\/h2>\n\n\n\n

Credit Hours:<\/strong> 3
Semester Taught:<\/strong> Fall\/Spring
Textbook<\/strong>: Introduction to the Theory of Computation, Third Edition, Michael Sipser. 2013<\/p>\n\n\n\n

\n\n\n\n

Course Objectives
<\/h2>\n\n\n\n
    \n
  • Introduce concepts in automata theory and theory of computation<\/li>\n\n\n\n
  • Identify different formal language classes and their relationships<\/li>\n\n\n\n
  • Design grammars and recognizers for different formal languages<\/li>\n\n\n\n
  • Prove theorems in automata theory and language properties<\/li>\n\n\n\n
  • Determine the decidability and intractability of computational problems<\/li>\n<\/ul>\n\n\n\n
    \n\n\n\n

    Prerequisites
    <\/h2>\n\n\n\n
      \n
    • CptS 122\/132<\/strong> – Data Structures<\/li>\n\n\n\n
    • Math 216<\/strong> – Discrete Structures<\/li>\n<\/ul>\n\n\n\n
      \n\n\n\n

      Learning Outcomes<\/h2>\n\n\n\n

      At the conclusion of this course students will:<\/p>\n\n\n\n

        \n
      • Have acquired a fundamental understanding of the core concepts in automata theory and
        formal languages<\/li>\n\n\n\n
      • Be able to design grammars and automata (recognizers) for different language classes<\/li>\n\n\n\n
      • Be able to identify formal language classes and prove language membership properties<\/li>\n\n\n\n
      • Be able to prove theorems establishing key properties of formal languages and automata<\/li>\n\n\n\n
      • Have acquired a fundamental understanding of core concepts relating to the theory of computation and computational models including decidability and intractability<\/li>\n<\/ul>\n\n\n\n
        \n\n\n\n

        Topics
        <\/h2>\n\n\n\n
          \n
        1. Introduction to automata theory<\/li>\n\n\n\n
        2. Finite Automata (DFA and NFA)<\/li>\n\n\n\n
        3. Regular expressions and languagues<\/li>\n\n\n\n
        4. Properties of regular languages: pumping lemma, closure properties, decision properties, equivalence and minimization of automata<\/li>\n\n\n\n
        5. Context-free grammars and languages<\/li>\n\n\n\n
        6. Pushdown Automata<\/li>\n\n\n\n
        7. Properties of context-free languages<\/li>\n\n\n\n
        8. Turing machines and extensions<\/li>\n\n\n\n
        9. Undecidability, diagonalization, problem reduction<\/li>\n\n\n\n
        10. Intractable problems: P and NP, NP-completeness<\/li>\n<\/ol>\n\n\n\n
          \n\n\n\n

          Weekly Schedule<\/h2>\n\n\n\n

          This is an example of what the week-by-week schedule of topics and assignments would look like. <\/p>\n\n\n\n

          WEEKS <\/th>TOPICS <\/th>ASSIGNMENTS <\/th><\/tr>
          01 <\/td>Intro to course, intro to computation theory<\/td>HW0 (survey) out<\/td><\/tr>
          02 <\/td>Review of math concepts, proof
          techniques, finite automata<\/td>          		HW0 in; HW1 out<\/td><\/tr>
          03 <\/td>Finite Automata<\/td>No class 9\/2; HW1 in, HW2 out<\/td><\/tr>
          04 <\/td>Regular Expressions<\/td>HW2 in, HW3 out<\/td><\/tr>
          05 <\/td>Nonreguar Languages<\/td>HW3 in<\/td><\/tr>
          06 <\/td>Context-free Languages<\/td>Mid-term 1 on 9\/25<\/td><\/tr>
          07 <\/td>Context-free Grammars<\/td>HW4 out<\/td><\/tr>
          08 <\/td>Pushdown Automata<\/td>HW4 in, HW5 out<\/td><\/tr>
          09 <\/td>CFG and PDA equivalence<\/td>HW5 in<\/td><\/tr>
          10 <\/td>Minimization of Automata; Deterministic CFL<\/td>Review for Mid-term 2<\/td><\/tr>
          11 <\/td>Turing Machines I<\/td>Mid-term 2 (10\/28); HW 6 Out<\/td><\/tr>
          12 <\/td>Turing Machines II<\/td>HW6 in<\/td><\/tr>
          13 <\/td>Decidability<\/td>No class 11\/11; HW 7 out<\/td><\/tr>
          14 <\/td>Reducibility<\/td>HW 7 in<\/td><\/tr>
          15 <\/td>Thanksgiving break<\/strong><\/td><\/td><\/tr>
          16 <\/td>Time Complexity, Review<\/td>Practice<\/td><\/tr>
          17 <\/td>Finals Week<\/td>Final Exam on Dec 9<\/td><\/tr><\/tbody><\/table><\/figure>\n","protected":false},"excerpt":{"rendered":"

          CptS 317: Automata and Formal Languages Course Information Credit Hours: 3Semester Taught: Fall\/SpringTextbook: Introduction to the Theory of Computation, Third Edition, Michael Sipser. 2013 Course Objectives Prerequisites Learning Outcomes At the conclusion of this course students will: Topics Weekly Schedule This is an example of what the week-by-week schedule of topics and assignments would look […]<\/p>\n","protected":false},"author":12156,"featured_media":0,"parent":1040,"menu_order":1,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"categories":[],"tags":[],"university_category":[],"location":[],"organization":[],"_links":{"self":[{"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/pages\/1032"}],"collection":[{"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/users\/12156"}],"replies":[{"embeddable":true,"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/comments?post=1032"}],"version-history":[{"count":11,"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/pages\/1032\/revisions"}],"predecessor-version":[{"id":1701,"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/pages\/1032\/revisions\/1701"}],"up":[{"embeddable":true,"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/pages\/1040"}],"wp:attachment":[{"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/media?parent=1032"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/categories?post=1032"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/tags?post=1032"},{"taxonomy":"wsuwp_university_category","embeddable":true,"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/university_category?post=1032"},{"taxonomy":"wsuwp_university_location","embeddable":true,"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/location?post=1032"},{"taxonomy":"wsuwp_university_org","embeddable":true,"href":"https:\/\/labs.wsu.edu\/scads\/wp-json\/wp\/v2\/organization?post=1032"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}