per person /

Free

Home Courses

Formal Languages Automata Theory

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

VIRTUAL LAB

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

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

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 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 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 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 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 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 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 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

Our Main Teachers

A Avinash

Asst Professor
VIEW PROFILE

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  

Mrs.B.Sowjanya

Assistant Professor
VIEW PROFILE

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 […]

Abhijit Pal

Assistant Professor
VIEW PROFILE