What is (not) a computer, The idea of computing, Computing Machines and Languages,What is the Science of Computing, Programming. Data Structures, Algorithms and Science,Birth of Science computing, Computability, Undecideability, Intractability and Intelligence,Why Study Science computing and Key Ideas, Automata- The idea of computingMachine, Automata Definition, Constructing Simple Automata, Handling End Condition,Handling Reject States, A Step-by-Step model for constructing Automata, States as Memory,Why Finite number of states, Constructing more complex Automata, Mantras for constructingAutomata, Limitations of Finite Automata, Automata with Combinatorial States
The idea of Non-Determinism, Constructing Non-Deterministic Automata, EliminatingNon-Deterministic: converting NFA to DFA, Jumping States without Input, A method forminimizing Automata, Finite State Transducers, The idea of formal languages, Languagesof Automata, Regular Expression, Constructing Regular Expressions, Converting RegularExpressions to Automata, Equivalence of Regular Expressions, Method for ConstructingRegular Expressions, Regular Expressions in Practice
The idea of Grammar, The ideas of parsing and Derivation, Grammars for RegularLanguages, Constructing Regular Grammars, converting automata to regular grammars,converting regular grammars to automata, constructing regular grammars: mantras, Closureproperties, Answering questions about regular languages, Why are some languages notregular, The Pigeonhole Principle and Pumping Lemma, Using Pumping Lemma anAdversarial Game.
The idea and nature of context free grammar, Constructing Context free grammars (LGs andNon LGs), Introduction to Parsing, Ambiguity and Eliminating ambiguity, The idea ofChomsky normal form, Converting to Chomsky normal form, The ideas of Griebach Normalform, Simple Linear and other grammars.
Machines for Context Free Languages, Adding Memory: Why Stack Behavior,Constructing PDAs, Constructing CFGs to PDAs, Converting PDAs to CFGs, Nondeterminismin PDAs, The CFL-CFG-PDA Triad, Closure Properties, Union of CFLs,Answering Questions about CFLs, Why are some languages not context-free, The pumpinglemma for context free languages.
The ideas of Universal Computing Machine, Constructing simple Turing machines,Constructing more complex Turing machines, Mantras for Constructing TuringMachines, The ideas of computation, computable functions, The Church-Turing Thesis,Variations of Turing Machines, The Universal Turing Machine
Languages, Grammars and Machines, Recursively Enumerable Languages, CountingAlphabets, Languages and Computing Machines, The idea of Enumeration, The idea ofDiagnoalization, The ideas of Acceptance and Membership, Recursive Languages, ContextSensitive Languages and Grammars, The ideas of context, Other Grammars and Automata,Linear and Deterministic Context-Free Langauges.