TAS2001 | Background - Automata Theory | A Simple State Machine | Download | |
TAS2002 | Languages | Define Language, Set Forming Notation, Kleen Star | Download | |
TAS2003 | Recursive Definition of Languages | Multiple Examples of Recursive Languages | Download | |
TAS2004 | Regular Expression | Descriptive Language vs RE | Download | |
TAS2005 | Finite Automata | DFA, Transition Table, Applications | Download | |
TAS2006 | Transition Graphs | Introduction to First NFA Theoretical Machine | Download | |
TAS2007 | Kleen's Theorem | Non-Deterministic Finite Automata | Download | |
TAS2008 | Finite Automata with Output | Moore and Mealy Machines | Download | |
TAS2009 | Regular Languages | Complement of a Language | Download | |
TAS2010 | Non-Regular Languages | The Pumping Lemma | Download | |
TAS2011 | Decidability | Membership, Empty and Infinite Problems | Download | |
TAS2012 | Context Free Grammar | Production and Derivation, Parse Trees | Download | |
TAS2013 | Grammatical Format | CFL to RL, Unit and Null Productions, CNF | Download | |
TAS2014 | Push Down Automata | PDA Language | Download | |
TAS2015 | CFG = PDA | Constructive Algorithm | Download | |
TAS2016 | Non-Context-Free Languages | Pumping Lemma for CFLs | Download | |
TAS2017 | Context-Free Languages | Union, Concatenation, Kleen Star, Intersection | Download | |
TAS2018 | Decidability (CFLs) | Membership, Emptiness and Finiteness Problems | Download | |
TAS2019 | Turing Machines | Program Rules, The Halting Problem | Download | |
TAS2020 | JFLAP | A Tool to develop Finite Automata | Download |
Introduction to Computer Theory 2nd Edition
By: Daniel I. Cohen
The course introduces some fundamental concepts in automata theory and formal languages including grammar, finite automaton, regular expression, formal language, pushdown automaton, and Turing machine. The course deals with the concept of computability and mathematical models, such as finite automata, grammars and Turing machines, and the relations between these models. The following topics are treated: Automata: finite automata, stack automata and Turing machines. Determinism and non-determinism. Regular expressions, transformation from regular expressions to finite automata and conversely, minimization of deterministic finite automata. Formal languages: grammars, Chomsky’s hierarchy, context-free grammars and regular grammars, closure properties. The relation between grammars and variants of automata. The pumping lemmas for regular and context-free languages, respectively. The universal machine, the halting problem and other undecidable problems.
Presenting the theory of finite automata, as the first step towards learning advanced topics, such as compiler design. | Applying the concepts learned in fundamental courses such as Discrete Mathematics, in a theoretical setting; in particular, the application of proof techniques. | Discussing the applications of finite automata towards text processing. | Developing an understanding of computation through Turing Machines