Difference between revisions of "User:Jeffj/CS4-5723/Syllabus"

From A-State Computer Science Wiki
Jump to: navigation, search
m (Jburleson moved page User:Jeff.jenness/CS4-5723/Syllabus to User:Jeffj/CS4-5723/Syllabus: Automatically moved page while renaming the user "Jeff.jenness" to "Jeffj")
 
(13 intermediate revisions by the same user not shown)
Line 2: Line 2:
 
{{TOCright|limit=3}}
 
{{TOCright|limit=3}}
 
== CS 4-5723 Automata Theory ==
 
== CS 4-5723 Automata Theory ==
Spring 2016, Section 001, TR 12:30pm-1:45pm, CSM 211 (moved to HSS 1028) (3 credits)
+
Spring 2020, Section 001, TR 12:30pm-1:45pm, CSM 212 (3 credits)
  
 
== Instructor ==
 
== Instructor ==
Line 10: Line 10:
 
{{:Courses/CS 4-5723/Description}}
 
{{:Courses/CS 4-5723/Description}}
  
=== CS 4723 Program Objectives ===
+
====Program Specific Outcomes====
* Computer Science undergraduate students will attain an ability to apply knowledge of computing and mathematics appropriate to the discipline.
+
* (Reinforced) {{:Degrees/BS/Outcomes/1}}
* Computer Science undergraduate students will attain an ability to analyze  problem and identify and define the computing requirements appropriate to its solution.
+
* (Reinforced) {{:Degrees/BS/Outcomes/8}}
* Computer Science undergraduate students will attain recognition of the need for and an ability to engage in continuing professional development.
+
* Computer Science undergraduate students will attain an ability to use current techniques, skills, and tools necessary for computing practice.
+
  
=== CS 5723 Program Objectives ===
+
====Program Specific Outcomes====
* M.S. Computer Science graduate students should have a deeper understanding of the theory and application of algorithms, programming languages, and computer processes.
+
* (Reinforced) {{:Degrees/MS/Outcomes/1}}
=== Course Objectives === <!-- OPTIONAL -->
+
 
 +
=== Course Objectives ===
 
{{:Courses/CS 4-5723/Objectives}}
 
{{:Courses/CS 4-5723/Objectives}}
  
=== Course Outcomes === <!-- OPTIONAL -->
+
=== Course Outcomes ===
 
{{:Courses/CS 4-5723/Outcomes}}
 
{{:Courses/CS 4-5723/Outcomes}}
 
   
 
   
Line 28: Line 27:
 
:<table border=0><tr><th align=left>Tests (3)</th><td></td><td>70%</td></tr><tr><th align=left>Final</th><td></td><td>30%</td></tr></table>
 
:<table border=0><tr><th align=left>Tests (3)</th><td></td><td>70%</td></tr><tr><th align=left>Final</th><td></td><td>30%</td></tr></table>
  
=== Schedule === <!-- OPTIONAL -->
+
=== Schedule ===
 
''(subject to change)''
 
''(subject to change)''
 
<table border=0>
 
<table border=0>
Line 34: Line 33:
 
<tr><td align=center valign=top>1</td>
 
<tr><td align=center valign=top>1</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 1</td><td valign=top></td></tr>
+
     <td valign=top>Chapter 1: Introduction to finite state machines</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>2</td>
 
<tr><td align=center valign=top>2</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 2.1-3</td><td valign=top></td></tr>
+
     <td valign=top>Chapter 1: Formal definitions, Proofs of closure of operations</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>3</td>
 
<tr><td align=center valign=top>3</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 2.4-5</td><td valign=top></td></tr>
+
     <td valign=top>Chapter 1:.Nondeterminism, proof of equivalence</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>4</td>
 
<tr><td align=center valign=top>4</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 3.1-2</td><td valign=top></td></tr>
+
     <td valign=top>Chapter 1: Regular Expressions, proof of equivalence</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>5</td>
 
<tr><td align=center valign=top>5</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 3.3-4.1</td><td valign=top></td></tr>
+
     <td valign=top>Chapter 1: Pumping Lemma and non-regular languages</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>6</td>
 
<tr><td align=center valign=top>6</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 4.2-3</td><td valign=top></td></tr>
+
     <td valign=top>Chapter 1: Applications of Pumping Lemma</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>7</td>
 
<tr><td align=center valign=top>7</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 4.4</td><td valign=top></td></tr>
+
     <td valign=top>Review and Test</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>8</td>
 
<tr><td align=center valign=top>8</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 5.1-2</td><td valign=top></td></tr>
+
     <td valign=top>Chapter 2: Context-free languages, grammars and ambiguity</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>9</td>
 
<tr><td align=center valign=top>9</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 5.3-4</td><td valign=top></td></tr>
+
     <td valign=top>Chapter 2: Nondeterministic Push-down Automata</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>10</td>
 
<tr><td align=center valign=top>10</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 6</td><td valign=top></td></tr>
+
     <td valign=top>Chapter 2: Equivalence of CFG's and PDA's</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>11</td>
 
<tr><td align=center valign=top>11</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 7</td><td valign=top></td></tr>
+
     <td valign=top>Chapter 2: Pumping Lemma and Non-context-free languages</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>12</td>
 
<tr><td align=center valign=top>12</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 8</td><td valign=top></td></tr>
+
     <td valign=top>Chapter 2: Deterministic Context-free languages</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>13</td>
 
<tr><td align=center valign=top>13</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 9</td><td valign=top></td></tr>
+
     <td valign=top>Review and Test</td><td valign=top></td></tr>
 
<tr><td align=center valign=top>14</td>
 
<tr><td align=center valign=top>14</td>
 
     <td></td>
 
     <td></td>
     <td valign=top>Chapter 10</td><td valign=top></td></tr>
+
     <td valign=top>Review for Final</td><td valign=top></td></tr>
 
</table>
 
</table>
  
==== Dates to Remember ==== <!-- OPTIONAL -->
+
==== Dates to Remember ====
 
+
=== Assignments === <!-- OPTIONAL -->
+
 
+
==== Homework ==== <!-- OPTIONAL -->
+
  
 +
=== Assignments ===
 +
==== Homework ====
 
== Materials ==
 
== Materials ==
 
=== Textbook ===
 
=== Textbook ===
Line 94: Line 91:
 
}}
 
}}
  
=== Resources === <!-- OPTIONAL -->
+
=== Resources ===
:Go to the {{link|protocol=https://|address=magichat.cs.astate.edu/seafile/d/25975ae4ff|marquee=online repository}}
+
:Go to the {{link|protocol=https://|address=magichat.cs.astate.edu/d/81229e7afa/?p=/CS4-5723%20Automata%20Theory&mode=list|marquee=online repository}}
  
==== Software Downloads ==== <!-- OPTIONAL -->
+
==== Software Downloads ====
{{link|address=www.jflap.org|marquee=JFLAP}} is software for exploring and experimenting with automata, machines and grammars.  
+
{{link|address=www.jflap.org|marquee=JFLAP}} is software for exploring and experimenting with automata, machines and grammars.
  
 
== Course Policies ==   
 
== Course Policies ==   
 
See [[Department/Policies/Classroom|Department Policies]] which will be adhered to within the course.
 
See [[Department/Policies/Classroom|Department Policies]] which will be adhered to within the course.
  
== See Also == <!-- OPTIONAL -->
+
== See Also ==
 
* {{link|title=Mathematical Induction|address=en.wikipedia.org/wiki/Mathematical_induction|description=Wikipedia article}}
 
* {{link|title=Mathematical Induction|address=en.wikipedia.org/wiki/Mathematical_induction|description=Wikipedia article}}
  
 
<small>[{{fullurl:{{FULLPAGENAMEE}}|action=pdfbook&format=single}} create PDF version]</small>
 
<small>[{{fullurl:{{FULLPAGENAMEE}}|action=pdfbook&format=single}} create PDF version]</small>

Latest revision as of 12:45, 19 February 2020

CS 4-5723 Automata Theory

Spring 2020, Section 001, TR 12:30pm-1:45pm, CSM 212 (3 credits)

Instructor

Dr. Jeff Jenness
OfficeCSM 132Office HoursTR 11:00am-12:00pm and MW 11:00pm-12:00pm
Phone870-972-3978 ext. 8117Emailjeffj@astate.edu


Course Description

CS 4-5723.  Automata Theory
Study formal languages and equivalent models of computation, finite state automata and regular expressions, push down automata and context free grammars, pumping lemmas and closure properties, and turing machines. Prerequisites: CS 3113. Fall odd.


Program Specific Outcomes

  • (Reinforced) Graduates of the B.S./B.A. Computer Science degree program attain the ability to apply knowledge of computing and mathematics appropriate to the discipline.
  • (Reinforced) Graduates of the B.S./B.A. Computer Science degree program attain recognition of the need for and an ability to engage in continuing professional development.

Program Specific Outcomes

  • (Reinforced) M.S. Computer Science graduate students should have a deeper understanding of the theory and application of algorithms, programming languages, and computer processes.

Course Objectives

The student will perform basic proofs in the foundations of computer science. The student will understand some of the theory behind regular languages and automata. The student will be able to construct grammars, automata and turing machines.

Course Outcomes

  • Understand the basic principles behind mathematical induction
  • Be able to construct basic proofs for sets and languages
  • Understand the idea of deterministic and nondeterministic automata
  • Construct simple machines and grammars for a variety of languages
  • Prove properties for both regular and context-free languages
  • Be able to construct turing machines for solving problems

Grading

Grades are assigned on a standard scale with the following weights:

Tests (3)70%
Final30%

Schedule

(subject to change)

Week  TopicReadingAssignment
1 Chapter 1: Introduction to finite state machines
2 Chapter 1: Formal definitions, Proofs of closure of operations
3 Chapter 1:.Nondeterminism, proof of equivalence
4 Chapter 1: Regular Expressions, proof of equivalence
5 Chapter 1: Pumping Lemma and non-regular languages
6 Chapter 1: Applications of Pumping Lemma
7 Review and Test
8 Chapter 2: Context-free languages, grammars and ambiguity
9 Chapter 2: Nondeterministic Push-down Automata
10 Chapter 2: Equivalence of CFG's and PDA's
11 Chapter 2: Pumping Lemma and Non-context-free languages
12 Chapter 2: Deterministic Context-free languages
13 Review and Test
14 Review for Final

Dates to Remember

Assignments

Homework

Materials

Textbook

Introduction to the Theory of Computation, 3rd ed. (ISBN: 978-1133187790), by Michael Sipser. Course Technology, 2012. (Amazon)

Resources

Go to the online repository

Software Downloads

JFLAP is software for exploring and experimenting with automata, machines and grammars.

Course Policies

See Department Policies which will be adhered to within the course.

See Also

create PDF version