Theoretical Computer Science


Lectures

TOPIC ( Click to Download PPT)
Lec 1
0: Overview, mathematical notation, proof by induction ( pdfppt
Lec 2
0 and 1: Strings, String Operations, Languages (pdfppt
Lec 3 & 4
1.1:Introduction to Deterministic Finite Automata(DFA) , formal definition of a DFA, simple examples of DFA's (pdfppt
Lec 3 & 4
1.1: Designing Finite Automata, formal definition of computation (pdfppt)
Lec 5
1.1/1.2: Regular operations on Languages, Union closure of regular languages, motivation for and introduction to Nondeterministic Finite Automata (NFA) (pdfppt
Lec 6
1.2: Examples of NFA's, Introduction to converting NFA's to DFA's (pdfppt)
Lec 7
1.2: Converting NFA's to DFA's (pdfppt
Lec 8
1.2: Closure of Regular Languages (pdfppt
Lec 9
1.3: Regular Expressions (pdfppt
Lec 9
1.3: Regular Expressions (pdfppt
Lec
Regular Expressions and JFLAP SOFTWARE, GREP INTRODUCTION(ppt)
Lec
1.3:Regular Expressions and GNFA (ppt
Lec 10 & 11
1.4: Non-Regular Languages/Pumping Lemma part 1: (ppt) part 2: (ppt
Lec
Pumping Lemma Examples: (ppt)
Is { a^(2n) | n > 0 } non-regular? (ppt)
Lec 11
2.1: Context Free Grammars part 1: (ppt) part 2: (ppt
Lec 11 & 12
2.1 CFG part 1: (ppt) part 2: (ppt
Lec 13
2.2: Pushdown Automata (PDA) (ppt
Lec 14
2.2: Pushdown Automata (PDA) (ppt
Lec 14
2.2: Pushdown Automata (PDA), Chomsky Normal Form (CNF) (ppt
Lec 14
2.3/2.4: Non-Context Free Languages (ppt) Mid-Semester Course Evaluation (ppt
Lec 14 & 15
2.3/2.4: Non-Context Free Languages (ppt) (ppt
Lec 16
Parsing Introduction (Handout): (ppt
Lec 17
Parsing Introduction (Handout): (ppt)
  • Construction of LL(1) parsing table.
  • "Common prefixes" and "left recursion" problems.
Lec 18
LL(1) Parsing, Shift/Reduce Parsing (ppt)
(JFLAP examples: 1234
Lec 19
Lex & Yacc (pptExamples 
Lec
Linux Command line (ppt)
Lec 20
3.1: Turing Machines, Basic Examples, Formal Definition (ppt)
Lec 21
3.2: Turing Machines, More examples, Multitape machines (ppt)
Lec 22
4.1: Decidability, Examples of Decidable languages (ppt
Lec 23
4.2 Halting Problem (ppt)
Lec 23
4.2 Halting problem (ppt)
JFLAP Turing Machines (ppt)
Lec 24
7.1: Time Complexity Introduction, big-O notation (ppt)
Lec 25
7.2: Class P of languages, examples (ppt)

No comments: