per person /
Free
Formal Languages Automata Theory
Teacher
A Avinash
Category
Core Courses
Course Attendees
Still no participant
Course Reviews
Still no reviews
Course Name : Formal Language Automata Theory
Code(Credit) : CUTM1038(2-1-0)
Course Objectives
- This course covers the theoretical computer science areas of formallanguages and automata, computability and complexity. Topics covered include: regular and context-free languages; finite automata and pushdown automata; Turing machines; computability - halting problem, solvable and unsolvable problems.
- Study of the “lexical analyzer” of a typical compiler, that is, the compiler component that breaks the input text into logical units, such as identifiers, keywords, and punctuation; Software for scanning large bodies of text, such as collections of Web pages, to find occurrences of words, phrases, or other patterns.
Course Outcomes
| COs | Course outcomes | Mapping COs with POs (High-3, Medium-2, Low-1) |
| CO1 | Acquire a full knowledge and mentality of Automata Theory as the basis of all computer science languages design | PO1 (3)- Engineering Knowledge |
| CO2 | Analyze to compare algorithms with respect to time and space complexity | PO2(3)- Problem Analysis |
| CO3 | Solve different problems on concepts such as RE's, DFA's, NFA's, Stacks, Turing machines, and Grammars | PO2(3)- Problem Analysis |
| CO4 | Design FAs, NFAs, Grammars, languages modeling, small compilers basics etc. | PO3 (3)- Design / Development of Solutions |
| CO5 | Able to do research on different automata machines | PO4(1)- Investigations of Complex Problems |
Course Syllabus
Module-1: Finite Automata (3 Hrs(T) + 2 Hrs(P)
Introduction to Finite Automata; The central concepts of Automata theory; Finite Automata: NFA (with and without ε), DFA, FA conversions cycle, Reduced DFA
Practice
1.Finite Automata Design
2.Construction of NFA
3.Construction of DFA
4.Construction of DFA from RE
5.Construction of NFA from RE
6.Conversion of NFA with epsilon to NFA without epsilon
7.FA Conversion Cycle
8.Construction of Regular Expressions
Module-2: Regular languages(3 Hrs(T) + 2 Hrs(P)
Regular languages; Closure properties of regular languages, Decision properties of regular languages, Minimization of automata, Grammar – Types of Grammar - CFG and Languages–Derivations and Languages, Ambiguity Relationship between derivation and derivation trees.
Practice
1.Minimization of automata using JFLAP
2.Identification of grammar using JFLAP
3.Language generation using JFALP
4.Derivation tree generation using JFLAP
5.Left Most and Right Most Derivation
6.Minimization of CFG using JFLAP
7.Verification of Ambiguous grammar
8.Chomsky grammar verification using JFLAP
Module-3: Context-Free Languages(3 Hrs(T) + 2 Hrs(P)
Context-Free Languages: Simplification of CFG, Elimination of Useless symbols Unit productions - Null productions, Chomsky normal form, Problems related to CNF, CYK Algorithm.
Practice
1.Elimination of Useless symbols using JFLAP
2.Unit productions using JFLAP
3.Null productions using JFLAP
4.Chomsky normal formal using JFLAP
5.CFG to CNF using JFLAP
6.CFG to GNF using JFLAP
7.CYK algorithm implementation using JFLAP
Module-4: Pushdown Automata (3 Hrs(T) + 2 Hrs(P)
Pushdown Automata- Definitions – Moves, Instantaneous descriptions, Deterministic pushdown automata, Equivalence of Pushdown automata and CFL, pumping lemma for CFL
Practice
1.Construction of PDA using JFLAP
2.Construction of DPDA using JFLAP
3.Construction of NPDA using JFLAP
4.Construction of PDA from CFG
Module-5: Linear bounded Automata (3 Hrs(T) + 2 Hrs(P)
Linear bounded Automata, Context Sensitive Language, Chomsky Hierarchy of Languages and automata, Organization of Linear bounded Automata, Properties of context-sensitive languages.
Practice
1.Combine two automata using JFLAP
2.Minimization of FA using JFLAP
3.Identification of CFL using JFLAP
4.Implementation of LBA
5.Identification of Type-1 grammar using JFLAP
6. Check the properties of CFL using JFLAP
Module-6: Turing Machines(3 Hrs(T) + 2 Hrs(P)
Turing Machines- Formal definition of Turing machines, Instantaneous descriptions, Turing Machine as Acceptors Languages and functions, Turing Machine constructions.
Practice
1.Construction of One-Tape Turing Machine using JFLAP
2.Construction of Turing Machine for for language L = {0n1n2n | n≥1}
3.Construct a Turing Machine for a language L = {aibjck | ik} ∩ {aibjck | i>j>k or i>j>k}
4.Construction of Multi-Tape Turing Machine
Module-7: Decidable and undecidable problems and Compilers Basics(3 Hrs(T) + 3 Hrs(P)
Undecidability- Basic definitions, Decidable and undecidable problems, Properties of Recursive and Recursively enumerable languages, Phases of the compiler, Lex, Parsing Techniques
Practice
1. Design a lexical analyzer for a given language and the lexical analyzer should ignore redundant spaces, tabs, and newlines. It should also ignore comments. Although the syntax specification states that identifiers can be arbitrarily long, you may restrict the length to some reasonable value
2.Write a LEX program to identify whether a given line is a comment or not.
3.Write a LEX program to recognize strings under 'a', 'a*b+', 'abb'
4.Implementation of SRP using LEX program
5. Write a LEX program for constructing of LL (1) parsing.
6.Lex Program to Count the Number of Lines words, and Characters in the Input File
7.Lex program that distinguishes keywords, integers, floats, identifiers, operators, and comments.
8. Generate regular expressions for the language accepting all combinations of a's, over the set ∑ = {a}
9. Generate regular expression for the language accepting all combinations of a's except the null string, over the set ∑ = {a}
10. Generate regular expression for the language accepting all the string containing any number of a's and b's.
11.Lex program to count the number of words, small and capital letters, digits and special characters in a C file
12.Lex Program for infix to postfix conversion
13.Implementation of LL(1) Parser
14.Implementation of RD Parser
15.Implementation of LR parser
Textbooks
Automata and Computability, Dexter C. Kozen, Springer Publisher.
Introduction to Automata Theory, Languages and Computation, Hopcroft, Motwani, and Ullman, Pearson Publishers, Third Edition.
Principles of Compiler Design: M. Ganga Durga, T. G. Manikumar MJP Publisher, 06-Jun-2019.
References
Elements of the Theory of Computation, H. R. Lewis and C.H. Papadimitriou, Prentice Hall Publishers.
Introduction to Languages and the Theory of Computation, John. C. Martin, Tata McGraw-Hill.
Session Plan
Session 1
Introduction to Finite Automata; The central concepts of Automata theory
https://www.youtube.com/watch?v=Qa6csfkK7_I
https://www.slideshare.net/SampathKumarS11/11-the-central-concepts-of-automata-theory
PDF
Session 2
Session 3
FA conversions cycle, Reduced DFA
https://www.youtube.com/watch?v=SmT1DXLl3f4
https://www.youtube.com/watch?v=OKFrju0HB7k
https://www.geeksforgeeks.org/conversion-from-nfa-to-dfa/
PDF
Session 4
Practice
1.Finite Automata Design
2.Construction of NFA
3.Constrction of NFA from RE
4.Converion of NFA with epsilon to NFA without epsilon
Session 5
Practice
1.Construction of DFA
2.Construction of DFA from RE
3.FA Conversion Cycle
4.Construction of Regular Expressions
VLAB
Session 6
Regular languages; Closure properties of regular languages, Decision properties of regular languages
https://www.youtube.com/watch?v=9Y15O7_ydFk
https://www.geeksforgeeks.org/closure-properties-of-regular-languages/
PDF
Session 7
Minimization of automata, Grammar – Types of Grammar - CFG, and Languages
https://www.youtube.com/watch?v=XFQzzQVFtyg
https://www.tutorialspoint.com/automata_theory/chomsky_classification_of_grammars.htm
PDF
Session 8
Derivations and Languages, Ambiguity Relationship between derivation and derivation trees.
https://www.youtube.com/watch?v=u4-rpIlV9NI
https://www.gatevidyalay.com/parse-tree-derivations-automata/
PDF
Session 9
Practice
1.Minimization of automata usinf JFLAP
2.Identification of grammar usinf JFLAP
3.Left Most and Right Most Derivarion
4.Minimization of CFG using JFLAP
Session 10
Practice
1.Language generation using JFALP
2.Derivation tree generation using JFLAP
3. Verification of Ambiguous grammar
4. Chomsky grammar verification using JFLAP
Session 11
Context-Free Languages: Simplification of CFG, Elimination of Useless symbols Unit productions - Null productions
https://www.youtube.com/watch?v=EF09zxzpVbk
https://www.geeksforgeeks.org/simplifying-context-free-grammars/
PDF
Session 12
Chomsky normal form, Problems related to CNF
https://www.youtube.com/watch?v=Mh-UQVmAxnw
https://www.javatpoint.com/automata-chomskys-normal-form
PDF
Session 14
Practice
1.Elimination of Useless symbols using JFLAP
2.Unit productions using JFLAP
3.Null productions using JFLAP
4.CFG to CNF using JFLAP
5.CFG to GNF using JFLAP
Session 15
Practice
1.Chomsky normal formal using JFLAP
2.CYK algorithm implementation using JFLAP
Session 16
Pushdown Automata- Definitions – Moves
https://www.youtube.com/watch?v=4ejIAmp_Atw
https://www.slideshare.net/SampathKumarS11/3123-pushdown-automata-definition-moves-amp-id
PDF
Session 17
Instantaneous descriptions, Deterministic pushdown automata
https://www.youtube.com/watch?v=prZkUEpnIuA
https://www.tutorialspoint.com/automata_theory/pushdown_automata_introduction.htm
PDF
Session 18
Equivalence of Pushdown automata and CFL, pumping lemma for CFL
https://www.youtube.com/watch?v=FjGrU7vczyg
https://www.slideshare.net/SampathKumarS11/35-equivalence-of-pushdown-automata-and-cfl
PDF
Session 19
Practice
1.Constion of PDA using JFLAP
2.Construction of NPDA using JFLAP
Session 20
Practice
1.Construction of DPDA using JFLAP
2.Construction of PDA from CFG
Session 21
Linear bounded Automata, Context Sensitive Language.
https://www.youtube.com/watch?v=i3c_2c2KFpY
PDF
Session 22
Chomsky Hierarchy of Languages and automata,Organization of Linear bounded Automata
https://www.youtube.com/watch?v=AlSB2_CehbM
https://www.geeksforgeeks.org/chomsky-hierarchy-in-theory-of-computation/
Session 23
Properties of context-sensitive languages.
https://www.youtube.com/watch?v=i3c_2c2KFpY
https://www.geeksforgeeks.org/context-sensitive-grammar-csg-and-language-csl/
Session 24
Practice
1.Combine two automata using JFLAP
2.Minimization of FA using JFLAP
3.Check the properties of CFL using JFLAP
Session 25
Practice
1.Identification of CFL using JFLAP
2.Implementation of LBA
3.Idenfication of Type-1 grammar using JFLAP
Session 26
Turing Machines- Formal definition of Turing machines
https://www.youtube.com/watch?v=yFEdBR-rP9g
https://www.seas.upenn.edu/~cit596/notes/dave/turing2.html
PDF
Session 27
Instantaneous descriptions, Turing Machine as Acceptors Languages and functions
https://www.youtube.com/watch?v=zpMf0IEUi00
https://www.geeksforgeeks.org/turing-machine-in-toc/
Session 28
Session 29
Practice
1.Construction of One-Tape Turing Machine using JFLAP
2.Construction of Multi-Tape Turing Machine
Session 30
Practice
1.Construction of Turing Machine for for language L = {0n1n2n | n≥1}
2.Construct a Turing Machine for a language L = {aibjck | i<jj>k} ∩ {aibjck | i>j>k or i>j>k}
3.Construct a Turing Machine for a language L = {aibjck | ik} ∩ {aibjck | i>j>k or i>j>k}
4.Construct a Turing Machine for language L = {wwr | w ∈ {0, 1}}
5.Construct a Turing Machine for language L = {ww | w ∈ {0,1}}
Session 31
Undecidability- Basic definitions, Decidable and undecidable problems
https://www.youtube.com/watch?v=JfX7VK7ocRU
https://www.geeksforgeeks.org/decidable-and-undecidable-problems-in-theory-of-computation/
Session 32
Properties of Recursive and Recursively enumerable languages
https://www.youtube.com/watch?v=KzqImrmb38k
https://www.geeksforgeeks.org/recursive-and-recursive-enumerable-languages-in-toc/
Session 33
Phases of the compiler, Lex, Parsing Techniques
https://www.youtube.com/watch?v=VGgIZl5WjH0
https://www.youtube.com/watch?v=i7omPsPjsgo
https://www.tutorialspoint.com/compiler_design/compiler_design_architecture.htm
Session 34
Session 35
Practice
1. Design a lexical analyzer for a given language and the lexical analyzer should ignore redundant spaces, tabs and newlines. It should also ignore comments. Although the syntax specification states that identifiers can be arbitrarily long, you may restrict the length to some reasonable value
2.Write a LEX program to identify whether a given line is a comment or not.
Session 36
Practice
1.Write a LEX program to recognize strings under 'a', 'a*b+', 'abb'
2. Generate regular expressions for the language accepting all combinations of a's, over the set ∑ = {a}
3. Generate regular expression for the language accepting all combinations of a's except the null string, over the set ∑ = {a}
4.Generate regular expression for the language accepting all the string containing any number of a's and b's.
Session 37
Top-down and Bottom-Up Parsers
https://www.youtube.com/watch?v=UR6B5RoYOLQ
https://www.tutorialspoint.com/compiler_design/compiler_design_top_down_parser.htm
Session 38
Practice
1.Lex Program to Count the Number of Lines words,and Characters in the Input File
2.Lex program that distinguishes keywords, integers, floats, identifiers, operators, and comments.
Session 39
Practice
1.Implementation of RD Parder
2.Implementaton of LR parser
Case Studies
ASSIGNMENT : https://drive.google.com/file/d/1Y_KZ6EbLZu3aIYu6erd81R3sT1MXa1fS/view?usp=drive_link
QUESTION BANK : https://drive.google.com/file/d/1hoWient0YsT3R8piw62br8km1JaBUxLz/view?usp=drive_link
Our Main Teachers
A.Avinash working as Assistant Professor, Dept of CSE, Centurion University of Technology and Management, Andhra Pradesh . Interested to work on Machine learning,Natural Language Processing,Problem Solving Methodologies , and ChatBot. Programming Skill: C Programming Data Structure Object Oriented Programming using C++ Formal Language Automata Theory Python Web Development(HTML,CSS,PHP) Database Management Systems Compilers
B.Sowjanya working as Assistant Professor, Dept of CSE, Centurion University of Technology and Management, Andhra Pradesh . Interested to work on Computer Networks,Databases,Artificial Intelligence and Machine Learning. Programming Skill: C Programming ,Data Structure, Object Oriented Programming using C++,JAVA Programming, Formal Language Automata Theory ,Python Web Development(HTML,CSS,PHP) Database Management Systems.
Prof. Susanta Kumar Nayak Working as Assistant Professor in Department of Computer Science & Engineering, Centurion University of Technology & Management, paralakhemundi,odisha . He completed MCA, MBA(HR), Ph.D. [(Pursuing). He has been an Academician from last 16.5 years. Previously he Worked as Assistant Professor in MCA Programme in Bharati Vidyapeeth Deemed University, Pune, Institute of Management Kolhapur […]