Instructor: Prof. Bhagi Narahari
Prerequisites: Software enginerring (CS 2113), Discrete Math ( CS1311), and Computer Architecture (CS 2461) (See undergraduate curriculum).


  • Class meets: Tuesday, Thursday 4:45 - 6:00pm

Office Hours:
Check Piazza for most updated ones.

Online Platforms

  • Piazza for discussions
  • Blackboard (Grades, Synchronous lectures, Homeworks)
  • Webpage - course slides, recordings, tutorials, links to software

Course Staff:

Course Description and Learning Outcomes

This is a core undergraduate Computer Science course on the theory of computing. The course introduces the foundations of computer computer science including questions such as “what is computation”, “what are the mathematical models of computing machines”, “what are the formal models to define languages, including syntax of programming languages”, “what is a computable problem”. The course covers these questions and in the process introduces important concepts such as Turing machines, formal languages, models of automata, theory behind parsing (the first stage in a compiler), and algorithms for parsing and design of finite state machines. Topics covered include: finite state automata and regular languages, context free grammars and pushdown automata, Turing machines and computability. This is a theoretical course and requires rigorous mathematical analysis, including deriving formal proofs, which will help you develop your on mathematical and abstraction skills. The lecture, and some lab sessions, will consist of in-class activities and students will be required to work in groups.

By the end of this course, students will be able to:

  • Understand key concepts in the theoretical foundations of computer science including: automata models such as finite state automata, pushdown automata and Turing machines; formal languages and grammars including regular languages, context free grammars and theory of parsing; Turing computability and the language hierarchy, and computational complexity.
  • Identify relationship between languages and computability including the language/machine hierarchy.
  • Understand the foundations and design algorithms for lexical analysis and parsing of programming languages.
  • Develop the ability fo read and construct mathematical models and proofs to determine complexity of machine models, and the limits and features of different classes of languages/machines/grammars.
  • Further develop the ability to abstract computational problems and develop mathematical perspective to problem solving.

Course Outline

  • See the course webpage for weekly schedule

Textbook and Resources

There are two options for a textbook; the instructor recommends the book by Linz but in both options there will be additional material provided by the instruction team.


  • JFLAP Automata Simulator: this is an automata simulation tool that we will be using to design and test automata.

  • Lab Sections * You must be registered in a lab section – both sections meet on Tuesday 9:35am. These will be conducted by the TAs. The Labs will be held on Blackboard. The labs will review material but will also include exercises, quizzes and discussions.

Workload and Grading

The course will be taught using a combination of recorded video lectures (and tutorials) and live synchronous sessions. As a 3 credit course, it will require a minimum of 2.5 hours per week of direct instruction and minimum of 5 hours of independent learning. In addition, the laboratory section will require 75 minutes of direct instruction and will include independent learning exercises and additional software tools to assist in your learning. Over the course of the semester, your independent learning will include watching video recordings, readings (lecture notes and/or textbook), and homeworks. The synchronous sessions will include lecture summaries, exercises and discussions. All synchronous sessions will be conducted using Blackboard Collaborate, and recordings of most of these sessions will be provided on blackboard.


  • 25%: Quizzes and Class participation. Quizzes will be held either during the lab or during the lecture session. Late arrival means you will miss the quiz - no extra time will be provided for those who arrive late. On average there will be a quiz scheduled approximately every week except during the weeks of the two exams and the first week of class. I will ignore one lowest score on your quizzes when computing the grade.
* Class Participation: The grades for class participation will be based on the required in-class exercises (as a group) during the lab or lecture sessions. There will be a number of these in-class exercises (during the lecture  and/or  during the lab), and the exercises will be given out during class. In addition, some of these assignments will be posted ahead of time so I expect that you will discuss  and come to class prepared to answer the questions  
  • 25%: Homeworks. A number of homeworks will be assigned. The goal of the homeworks is to improve your learning of the concepts covered in the lectures. No collaboration of any kind on the homeworks.

  • 50%: Three exams.
    * There will be two (midterm) exams, one covering regular languages and finite automata and the second covering context free languages. The final exam will be comprehensive but will focus mostly on content after the second exam.

Final Grading

  • Do I curve the grades? Yes.
  • Grades will be based on the ‘weighted total’ after curving and scaling, where the weights for each catergory are shown above - normalization places your total as a percentage of the highest total in the class, and curving identifies clusters.
  • Grades in each category and your weighted total will be posted on blackboard.
  • Grades are skewed toward the higher end if course average (or median) is high and skewed towards lower if they are low.
  • Grades are then approximately (since they will depend on the final distribution, including median score) assigned in the following ranges when the assumption is that the normalized average or median is around 78-80. Grades are skewed toward the higher end if average is higher and skewed towards lower if average is lower.
Percentage Letter grade
90-100 A range (A- to A)
80-89 B range (B- to B+)
70-79 C range (C- to C+)
60-69 D range (D- to D+)
below 60 F

Course Policies

If you have a disability, or a health or a family emergency, that may effect your participation in this course and wish to discuss academic accommodations, please contact me as soon as possible.

Late work policy: There are no late submissions allowed in this course. The only exception to this rule is if you have a medical or family emergency, and you should contact the instructor or the TA Andy Feng before the due date.

Grades will be posted on Blackboard – make sure you check and inform the instructors if you see any disparity between what is posted on blackboard and what you think your grades are. You have one week after the grades are posted to contact the instructor – after that there will be no regrading.

Email policy: You can send email to my GW email address. I will answer most class email during specific times set aside during the week for this purpose - so do not expect an instantaneous response. We encourage you to post questions on Piazza since that will be monitored by the entire instruction team and your classmates.

Illness policy: If you are ill and it will cause you to miss class, lab, or an assignment, you should let me know in advance if possible. I cannot extend deadlines unless you contact me. You are still responsible for all material you missed, which generally will be available on the course website or on blackboard.

Academic Integrity policy: It is very important in this course (and in life), that your work be your own. These guidelines will help you achieve that.

You must:

  • Do your best to solve all homework, quizzes, and exams on your own.
  • Notify me if you are using a tutor (this is not a problem, just let me know).

You may:

  • Discuss general approaches to solving the homework problems with other students by referring to questions in the textbook.
  • Discuss general mathematical concepts (proof techniques, formalisms, etc.) with another student although it is recommended that you contact one of the TAs or LAs for this purpose.

You may not:

  • Copy homework solutions from other students or people (or places/web) outside of the class.
  • Have someone else complete your homework for you.
  • Copy solutions from the internet.
  • Write solution as a group and then submit identical or slightly modified versions—if you discuss general approaches to solving a problem together, you still must be writing up your own independent solution.

The Academic Integrity Code will apply to this course. Please read through the code carefully. Penalties for violating the code or the policies described here include failing this course, and are elaborated in the GW Academic Integrity Code. Note that the minimum punishment is failure of the assignment.

Support for students outside the classroom.

  • Virtual Academic Support A full range of academic support is offered virtually in fall 2020. See Coronavirus FAQs for updates. Tutoring and course review sessions are offered through Academic Commons in an online format. See Academic Commons Coaching, offered through the Office of Student Success, is available in a virtual format. See Student Success. Academic Commons offers several short videos addressing different virtual learning strategies for the unique circumstances of the fall 2020 semester. See Study Skills. They also offer a variety of live virtual workshops to equip students with the tools they need to succeed in a virtual environment. See Virtual Learning.

  • Academic Commons. Academic Commons provides tutoring and other academic support resources to students in many courses. Students can schedule virtual one-on-one appointments or attend virtual drop-in sessions. Students may schedule an appointment, review the tutoring schedule, access other academic support resources, or obtain assistance at
  • Disability Support Services (DSS) 202 994 8250. Any student who may need an accommodation based on the potential impact of a disability should contact Disability Support Services to establish eligibility and to coordinate reasonable accommodations.
  • Counseling and Psychological Services. 202 994 5300. GW’s Colonial Health Center offers counseling and psychological services, supporting mental health and personal development by collaborating directly with students to overcome challenges and difficulties that may interfere with academic, emotional, and personal success. See Health Center.