Course Number / Section:

CIS 8513 / 001

Course Title:

Automata and Formal Languages


Dr. Arthur T. Poe


Wachman Hall, Room 1008.




Course Web Page:


Web Site for Complete  Syllabus:




CIS 500 or CIS166 and CIS242




 “Machines ,Languages, and Computation” by Denning, Dennis, and  Qualitz,  Prentice-Hall. ( Reprint )


Course Goals:





The course is “ to explore the three underlying themes of the theory of computation”: Abstract Machines, Languages and Computability. We will try to give an integrated presentation of the results in these areas, showing their relations and equivalences. The development is formal but most proofs are constructive.  The use of language theory concepts will have applications in engineering, compiler design, software specification, network protocol and complexity analysis.


Topics Covered:






Type of grammars. Finite Automata and regular leagues.  Kleene’s theorem. Closure properties and decidable questions of regular languages. Derivation Trees. Normal forms of context free Grammar. Closure properties and decidable questions of context-free languages. Self--embedding property. Push down automata and their equivalence to context free grammar. Two definitions of Contest sensitive grammar and their equivalence.  Kuroda Normal Form for csg. Turing Machines.





Attendance Policy:


            Attendance will be taken during lectures.