Still no participant

Still no reviews

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

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 |

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

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

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

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

**Practice**

1.Construction of DFA

2.Construction of DFA from RE

3.FA Conversion Cycle

4.Construction of Regular Expressions

VLAB

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

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

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

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

**Practice**

1.Language generation using JFALP

2.Derivation tree generation using JFLAP

3. Verification of Ambiguous grammar

4. Chomsky grammar verification using JFLAP

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

Chomsky normal form, Problems related to CNF

https://www.youtube.com/watch?v=Mh-UQVmAxnw

https://www.javatpoint.com/automata-chomskys-normal-form

PDF

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

**Practice**

1.Chomsky normal formal using JFLAP

2.CYK algorithm implementation using JFLAP

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

Instantaneous descriptions, Deterministic pushdown automata

https://www.youtube.com/watch?v=prZkUEpnIuA

https://www.tutorialspoint.com/automata_theory/pushdown_automata_introduction.htm

PDF

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

**Practice**

1.Constion of PDA using JFLAP

2.Construction of NPDA using JFLAP

**Practice**

1.Construction of DPDA using JFLAP

2.Construction of PDA from CFG

Linear bounded Automata, Context Sensitive Language.

https://www.youtube.com/watch?v=i3c_2c2KFpY

PDF

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/

Properties of context-sensitive languages.

https://www.youtube.com/watch?v=i3c_2c2KFpY

https://www.geeksforgeeks.org/context-sensitive-grammar-csg-and-language-csl/

**Practice**

1.Combine two automata using JFLAP

2.Minimization of FA using JFLAP

3.Check the properties of CFL using JFLAP

**Practice**

1.Identification of CFL using JFLAP

2.Implementation of LBA

3.Idenfication of Type-1 grammar using JFLAP

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

Instantaneous descriptions, Turing Machine as Acceptors Languages and functions

https://www.youtube.com/watch?v=zpMf0IEUi00

https://www.geeksforgeeks.org/turing-machine-in-toc/

**Practice**

1.Construction of One-Tape Turing Machine using JFLAP

2.Construction of Multi-Tape Turing Machine

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

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/

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/

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

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

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

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

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

**Practice**

1.Implementation of RD Parder

2.Implementaton of LR parser

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

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