Osmania Technology Business Incubator

Learning Path

Non-Linear: Random Order

About the Course

Course Description

This course provides a hands-on comprehensive study of Fundamentals of Automata, Formal Language Theory and Formal Languages/ Grammer Hierarchy, Finite Automata and Equivalent Automata, Minimization/ Optimization of DFA, Regular Expressions and Languages and Finite Automata and Regular Expressions, Transducers, Context-Free Grammers and Context-Free Languages and Simplication Free Context Free-Grammer and Turning Machine and TM Extensions and Languages.

Objectives

1.Will familiarize about Fundamentals of Automata- Computation, Finite State Machine

2.Will demonstrate Formal Language Theory- Symbols, Alphabets and Strings, Operations on Strings, Formal Languages, Operations on Languages.

3.Will develop knowledge in Minimization/ Optimization of DFA: Optimum DFA, Minimal DFA

Prerequisite

There is no particular prerequisite to learn Formal Languages and Automata Theory, you will be able to do very well, if you have these basic skills:

1. Basic Knowledge in programming

2. Good Computer Knowledge

3. Good communication skills

Course Study Materials

Module 1: Fundamentals of Automata

1.1 Fundamentals of Automata- Computation, Finite State Machine
1.2 Components of Finite State Automata and Elements of Finite State System, Mathematical representation of Finite State Machine
1.3 Automata Classification, Automata in Real World
Fundamentals of Automata-Assessment 10 Questions

Module 2: Formal Language Theory and Formal Languages/ Grammar Hierarchy

2.1 Formal Language Theory- Symbols, Alphabets and Strings, Operations on Strings, Formal Languages, Operations on Languages
2.2 Formal Languages/ Grammar Hierarchy: Formal Languages, Regular Language, Context-Free Language, Context-Sensitive Language, Recursive Language, Recursively Enumerable Language, Other Forms of Fo
2.3 Relationship between Grammars and Languages
Formal Language Theory and Formal Languages/ Grammar Hierarchy-Assessment 10 Questions

Module 3: Finite Automata and Equivalent Automata

3.1 Finite Automata: Introduction, Deterministic Finite Automata(DFA), Design of DFAs, Non Deterministic Finite Automata(NFA), Non-Deterministic Automata with Є-moves ,Design of NFA- Є s
3.2 Equivalent Automata: Equivalent Finite-State Automata, Equivalence of NFA/NFA- ɛ and DFA, Equivalence of NFA, with Є moves to NFA, without Є - moves.
Finite Automata and Equivalent Automata-Assessment 10 Questions

Module 4: Minimization/ Optimization of DFA, Regular Expressions and Languages and Finite Automata and Regular Expressions

4.1 Minimization/ Optimization of DFA: Optimum DFA, Minimal DFA
4.2 Two way DFA, DFA Vs 2DFA and Regular Expressions and Languages:Regular languages, Regular expressions, Components of Regular Expression,Properties of Regular Expressions
4.3 Finite Automata and Regular Expressions:Properties of Regular Sets and Regular Languages, Arden’s Theorem and Equivalence of Finite Automata and Regular Expressions, Equivalence of DFA and Regular
Minimization/ Optimization of DFA, Regular Expressions and Languages and Finite Automata and Regular Expressions-Assessment 10 Questions

Module 5: Transducers, Context-Free Grammars and Context-Free Languages

5.1 Transducers: Moore Machine, Mealy Machine, Difference between Moore and Mealy Machines, Properties / Equivalence of Moore and Mealy Machines and Context-Free Grammars and Context-Free Languages
5.2 Simplification of Context – Free Grammar: Simplification of Context-Free Grammars, Elimination of Є -Productions
5.3 Elimination of Unit Productions, Normal Forms for Context Free Grammars, Chomsky Normal Form, Greibach Normal Form, Chomsky Vs Greibach Normal Form, Application of Context- Free Grammars
Transducers, Context-Free Grammars and Context-Free Languages-Assessment 10 Questions

Module 6: Turing Machine, TM Extensions and Languages

6.1 Turing Machine: Introduction, Components of Turing Machine, Description of Turing Machine, Elements of TM, Moves of a TM, Language accepted by a TM,Role of TM’s , Design of TM’s and TM
Turing Machine, TM Extensions and Languages-Assessment 10 Questions

Final Assesment

Final Assesment 20 Questions

The certificate issued for the Course will have the student's Name, Photograph, Course Title, Certificate number, Date of course completion and the name(s) and logo(s) of the Certifying Bodies. Only the e-certificate will be made available. No Hard copies. The certificates issued by uLektz Learning Solutions Pvt. Ltd. can be e-verifiable at www.ulektzskills.com/verify.

Students are required to take online assessments with eProctoring.
Students will be assessed both at the end of each module and at the end of the Course.
Students scoring a minimum of 50% in the assessments are considered for Certifications