ITEC 420 - Computability Theory and Formal Languages

Fall 2019

Instructor: Dr. Okie, 219 Davis Hall

Phone: Office: 831-5992; Home: 951-7372 (Before 9:00 p.m., please)

Email: nokie (Feel free to send email. I'll reply as quickly as possible.)

Office Hours: MWF 2-3; TuTh: 11-12; and by appointment.

Lunch may occasionally require leaving a little early on TuTh. I will also typically be in MWF 1-2 if there are no department meetings. You are welcome to come by at any time, and I'd be glad to help you then or to set up an appointment otherwise. You may want to check my complete schedule to see when my meetings and classes are normally held.

Prerequisite: ITEC 122, Discrete Mathematics.

Content: In this course we focus on the theory of computation and, at the end, discuss the theory of complexity. The theory of computation deals with the theoretical limits of what can be computed and complexity theory deals with the practical limits. The heart of the course is languages, not natural languages (eg English), but formal languages, which are defined to be sets of strings (This will be on the exam!). We use a number of abstract tools for defining languages, including automata (Latin for machines), grammars, and regular expressions. Each of these tools is an abstract model of computing. We will also learn a hierarchy of languages and relate this hierarchy to a hierarchy of tools! The course involves little programming, but it does cover how the theory applies to real world computing.  The material in this course can be challenging, but it is also fascinating and stimulating, and I encourage you to give the course your best.

Topics:

  1. Mathematics background (as needed during semester)
  2. Languages
  3. Finite automata and regular expressions
  4. Nondeterministic automata
  5. Regular and context free languages
  6. Context free grammars
  7. Pushdown automata
  8. Turing Machines
  9. Undecidability
  10. NP-Completeness

Course Outcomes: Students who complete the course will be able to

  1. Demonstrate an ability to understand and apply mathematical concepts.
  2. Describe, analyze, and design language generators and recognizers including context free grammars and both deterministic and non-deterministic finite automata, pushdown automata, and Turing machines.
  3. Use a Pumping Lemma to prove that a language is not in a given class.
  4. Explain the Church-Turing Thesis and its significance.
  5. Describe example unsolvable problems and outline how a problem can be shown to be unsolvable.
  6. Define the classes P, NP, NP-Complete and explain their significance.

Required Text: Automata, Computability and Complexity: Theory and Applications, Elaine A. Rich, Prentice Hall, 2007.   This is an outstanding text!   It covers the field broadly, and at the same it time gives very clear descriptions of basic and advanced comcepts. Make sure that you look at the errata for the book at the author's book page which how contains a PDF copy of the text. .

Semester Schedule: We will cover most sections of chapters 1-21 and 27-30, but skipping chapters 4, 7, 15, and 29, and only briefly covering chapters 9 and 14. Exams will be held around the time we finish chapters 10 and 16.

Communication: I will post relevant course information on the course web page as well as send announcements via email.  It is your responsibility to be aware of this information, as well as all information presented in class, of course.

Course web page: http://www.radford.edu/nokie/classes/420. Currently this page shows topics and notes from earlier semesters, when we used different text. This semester we will primarily be using the excellent notes that come with the text, but I will leave the old notes as additional information. I will update topics as the semester progresses.

Evaluation: Course grades ("A" through "F", with pluses and minuses possible) will be based on your grades on the following activities:
Per cent Activity
40 Programs, Homework, and In-class Activities
30 Two in-class tests
30 Comprehensive final exam: 10:15 a.m. - 12:15 p.m., Monday, December 9, 2019
100 Total

$\newcommand{\TikZ}{\mathrm{Ti\textit kZ}}$ $\newcommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX}$

Homework problems: Every week or so you will have a graded set of homework problems. It is very important that you do these assignments; figuring out the answers to problems is the best way to learn the material.   Also, the assignments are worth 40% of your grade.   If there are 10 assignments, then each will be worth almost half of a letter grade for the course! Assignments will be graded on correctnesss and completeness, as well as neatness, clarity, and grammar.

Some students have enjoyed learning (or wish that they had learned!) $\LaTeX$, which is a macro language for $\TeX$, Knuth's powerful, Turing-Complete typesetting system for creating beautiful books). For practice and fun you can render online at arachnoid, quicklatex, and texrendr. Overleaf is a full-featured online system. Perhaps you'd also like $\TikZ$ (a $\LaTeX$ drawing package). One place to get a full $\TeX, \LaTeX, \rm{and }\ \TikZ$ is from MikTeX. I also use $\LyX$ (a WYSIWYM document processor for $\LaTeX$) for your exams and other documents.

Unless otherwise specified, assignments will be due in class and on paper. Electronic submissions will not be accepted. Please use the course grades page to verify that I recorded your grades correctly, and keep all graded work until after you have received your course grade.

Honor Code: This class will be conducted in strict observance of the Honor Code. Please refer to your Student Handbook for details of expected behavior.

Of course, all work that you submit for grading must be your own, not somebody else's. You must not let anyone write your assignments for you and you must not use someone else's solutions as a basis for your own.

You may form a study group and work together on solving the homework assignments. But each of you must understand for yourself how to solve each problem, and you must independently write up your own solution, in your own words, and submit it under your own name.

This means that you must not turn in work that is essentially identical with another person's.

Whenever possible you should show your work and explain your reasoning rather than simply giving a one-word answer to a question.

You should list the names of any students with whom you worked on an assignment, and you should also give a reference for any material that you find in a book or on the web.

Please be aware that if I suspect that you have violated the Honor Code, then I will not hesitate to file charges with the Dean of Students Office.

Late policy: Unless otherwise specified, late assignments will not be accepted.

You have two free late days that can be redeemed on any assignment(s). Please let me know when you are planning to use this option.

Attendance: Attendance is not required; however you will find it much easier to learn the material and to make a good grade if you come to class. If you get behind in this course you are likely to find it extremely difficult to catch up!  Learning the concepts takes time, and you must work on the course material regularly for it to sink in.  You will not be allowed to make up any in-class activities that you miss. Good attendance and class participation can be to your benefit if you have a borderline final grade!

Exams: In exceptional circumstances I may give permission to miss an exam if you contact me in advance. In such cases the weight of your final will be increased. Otherwise a missed exam will be worth 0 points.

Academic Accommodations: If you are seeking academic accommodations at RU under the ADA, you must register with the DRO. To receive academic accommodations for this class, submit your documentation to the DRO in Tyler Hall (lower level, Suites 54-69), 540-831-6525 (fax), or dro@radford.edu, and then set up an interview with the DRO to discuss accommodations. After you have been notified via email that your accommodation package is ready, you must pick it up and then meet with me to discuss it. For more information and documentation guidelines, visit www.radford.edu/dro or call 540-831-6350.

Distractions: Laptops and other electronic devices are not to be used during class without permission. Such devices are distracting to you and to others. Research shows that multitasking limits concentration and reduces learning. Experience shows that distraction from a laptop reduces a student's performance by a full letter grade. Food is also distractiong - please do not bring it to class! (Well, doughnuts for the entire class would prob'ly be okay!)


Dr. Okie's Home Page