CSCI 340

Computational Models

Coordinator: nazli hardy

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

At the end of the course, a successful student will be able to

  1. Demonstrate an understanding of various proof techniques. In particular, 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 deterministic pushdown automata and non-deterministic pushdown automata; apply these formalisms to practical programming problems.
  4. Understand the concept of Turing machines and their applications to computability.
  5. Explain the concepts of computable functions, 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