CSCI 340
Computational Models

Coordinator: Muhammad Chaudhary

Credits: 4.0

Description

Introduction to theory of computation. Topics include finite state automata, regular languages and grammars, pushdown automata, context-free languages and grammars, Turing machines, limits on algorithmic computation. Offered in spring.

Prerequisites

C- or higher in CSCI 140 and CSCI 162.

Sample Textbooks

Course Outcomes

 

 

 

1. Understating of various proof techniques. In particular, proofs by mathematical induction.  Be able to demonstrate the ability to carry out proofs by induction for simple problems.
2. Define, interpret, and construct deterministic finite-state automata and non-deterministic finite-state automata; define, interpret, and construct regular expressions; apply these formalisms to practical programming problems.
3. Define, interpret, and construct context free grammar; define, interpret, and construct deterministic pushdown automata and non-deterministic pushdown automata; apply these formalisms to practical programming problems.
4. Explain the history, scope, and limits of Artificial Intelligence. Discuss and understand the social, ethical, legal, and philosophical aspects of Al; not only be knowledgeable about various application areas of AI but also be able to use AI tools.
5. Understand parsing techniques and study their application to theory of compiler design.
6. Understand the concept of Turing machines  and their applications to computability.
7. Explain the concepts of computable function, the universal machine, the decision problem, and the difference between decidable and undecidable problems.

Major Topics Covered

1. Formal Languages
   1. Alphabets and strings
   2. Operations on strings
   3. Languages
   4. Operations on languages
2. Formal Grammars
   1. Phrase structure grammars
   2. Types of grammars and languages
      1. Regular
      2. Context-free
      3. Non-context-free
   3. Relationship between grammar and language types
3. Finite State Automata (FSA)
   1. Deterministic Finite State Automata (DFSA)
   2. Nondeterministic Finite State Automata (NFSA)
   3. Equivalent automata
   4. Equivalence of NFSA and DFSA
   5. Finite State Languages (FSL)
   6. Equivalence of FSL and regular languages
   7. Applications
4. Properties of Regular Languages
   1. Regular expressions (RE)
   2. Equivalence of RE and FSA
   3. Determining whether or not languages are regular
   4. Applications
5. Pushdown Automata (PDA)
   1. Deterministic Pushdown Automata (DPDA)
   2. Nondeterministic Pushdown Automata (NPDA)
   3. Non-equivalence of NPDA and DPDA
   4. Equivalence of NPDA and context-free languages
   5. Applications
6. Context-Free Languages (CFL)
   1. Relationship of CFL to regular languages
   2. Relationship of nondeterministic CFL to deterministic CFL
   3. Determining whether or not languages are context-free
   4. Applications
7. Parsing
   1. Top-Down Parsing
   2. Bottom-Up Parsing
   3. Applications
8. Turing Machines (TM)
   1. Deterministic Turing Machine (DTM)
   2. Nondeterministic Turing Machine (NTM)
   3. Equivalence of DTM and NTM
   4. TM to recognize languages
   5. TM to evaluate functions
9. I. Non-computability
   1. Church's Thesis
   2. The Halting Problem
   3. Unsolvable Problems About Turing Machines
   4. Unsolvable Problems About Grammars
10. Computational Complexity
    1. Time Complexity
    2. Space Complexity
    3. The Classes P and NP

Sample Laboratory Projects

 

Lab1:

http://www.cs.millersville.edu/~chaudhary/cs340/labs/2010lab1/index.htm

Lab2:

http://www.cs.millersville.edu/~chaudhary/cs340/labs/2010lab2/index.htm

Lab3:

http://www.cs.millersville.edu/~chaudhary/cs340/labs/2010lab3/index.htm

Lab4:

http://www.cs.millersville.edu/~chaudhary/cs340/labs/2010lab4/index.htm

Lab5:

http://www.cs.millersville.edu/~chaudhary/cs340/labs/2010lab5/index.htm

Lab6:

http://www.cs.millersville.edu/~chaudhary/cs340/labs/2010lab6/index.htm

Lab7:(SQL)

http://www.cs.millersville.edu/~chaudhary/cs340/labs/2010lab7/index.htm

 

 

Return to course directory.