KTU FLAT Introduces the principles of formal language theory and its application to computer science You can learn KTU subjects through our excellent study materials comprising of Notes, Presentations and Previous Years Question papers which are easily available on our website (www.keralanotes.com).
| Board | KTU |
| Scheme | 2019 New Scheme |
| Year | Third Year |
| Semester | S5 |
| Subject | Formal Languages & Automata Theory | CST 301 Notes |
| Credit | 4 Credit |
| Category | KTU S5 Computer Science |
KTU S5 FORMAL LANGUAGES AND AUTOMATA THEORY | CST 301 | Notes (2019 Scheme)
Module 1
Module 1 - Syllabus
Introduction to Formal Language Theory and Regular Languages:
Introduction to formal language theory– Alphabets, Strings, Concatenation of strings, Languages.
Regular Languages - Deterministic Finite State Automata (DFA) (Proof of correctness of construction not required), Nondeterministic Finite State Automata (NFA), Equivalence of DFA and NFA, Regular Grammar (RG), Equivalence of RGs and DFA.
Module 1 - Notes
Module 1 FORMAL LANGUAGES AND AUTOMATA THEORY | CST 301 PDF Notes
Module 2
Module 2 - Syllabus
More on Regular Languages:
Regular Expression (RE), Equivalence of REs and DFA, Homomorphisms, Necessary conditions for regular languages, Closure Properties of Regular Languages, DFA state minimization (No proof required).
Module 2 - Notes
Module 2 FORMAL LANGUAGES AND AUTOMATA THEORY | CST 301 PDF Notes
Module 3
Module 3 - Syllabus
Myhill-Nerode Relations and Context-Free Grammars:
Myhill-Nerode Relations (MNR)- MNR for regular languages, Myhill-Nerode Theorem (MNT) (No proof required), Applications of MNT.
Context-Free Grammar (CFG)- CFG representation of Context-Free Languages (proof of correctness is required), derivation trees and ambiguity, Normal forms for CFGs.
Module 3 - Notes
Module 3 FORMAL LANGUAGES AND AUTOMATA THEORY | CST 301 PDF Notes
Module 4
Module 4 - Syllabus
More on Context-Free Languages:
Nondeterministic Pushdown Automata (PDA), Deterministic Pushdown Automata (DPDA), Equivalence of PDAs and CFGs (Proof not required), Pumping Lemma for Context-Free Languages (Proof not required), Closure Properties of Context-Free Languages.
Module 4 FORMAL LANGUAGES AND AUTOMATA THEORY | CST 301 PDF Notes
Module 5
Module 5 - Syllabus
Context-Sensitive Languages, Turing Machines:
Context-Sensitive Languages - Context Sensitive Grammar (CSG), Linear Bounded Automata.
Turing Machines - Standard Turing Machine, Robustness of Turing Machine, Universal Turing Machine, Halting Problem, Recursive and Recursively Enumerable Languages. Chomsky classification of formal languages.
Module 5 - Notes
Module 5 FORMAL LANGUAGES AND AUTOMATA THEORY | CST 301 PDF Notes
KTU S5 CSE Related Links
| KTU S5 CSE Syllabus | Click Here |
| KTU S5 CSE Study Notes | Click Here |
| KTU S5 CSE Reference Textbook | Click Here |
| KTU S5 CSE Previous Year Solved Questions | Click Here |
| KTU S5 CSE Study Materials | Click Here |
Other Related Links
| CST 301 Formal Languages and Automata Theory | Click Here |
| CST 303 Computer Networks | Click Here |
| CST 305 System Software | Click Here |
| CST 307 Microprocessors and Microcontrollers | Click Here |
| CST 309 Management of Software Systems | Click Here |
| MCN301 Disaster Management (Non - Credit) | Click Here |
| CSL 331 System Software and Microprocessors Lab | Click Here |
| CSL 333 Database Management Systems Lab | Click Here |
