# Formal Languages and Automata Theory

Course Code:ULZ0203

Author:uLektz

University:

Regulation:2017

Categories:Computer Science

Format : ePUB3 (DRM Protected)

Type :eBook

Rs.189 Rs.28 Rs.85% off

Description :Formal Languages and Automata Theory of ULZ0203 covers the latest syllabus prescribed by General for All University for regulation 2017. Author: uLektz, Published by uLektz Learning Solutions Private Limited.

Note : No printed book. Only ebook. Access eBook using uLektz apps for Android, iOS and Windows Desktop PC.

##### Topics
###### UNIT I: FUNDAMENTALS OF AUTOMATA

1.1 Fundamentals of Automata- Computation, Finite State Machine

1.2 Components of Finite State Automata

1.3 Elements of Finite State System , Mathematical representation of Finite State Machine

1.4 Automata Classification, Automata in Real World

###### UNIT II: 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 Formal Languages

2.3 Relationship between Grammars and Languages

###### UNIT III: 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, Advantages of Non-Deterministic Finite Automata, NFA Versus DFA

3.2 Equivalent Automata: Equivalent Finite-State Automata, Equivalence of NFA/NFA- ɛ and DFA, Equivalence of NFA, with Є moves to NFA, without Є - moves.

###### UNIT IV: 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

4.3 Regular Expressions and Languages:Regular languages, Regular expressions, Components of Regular Expression, Properties of Regular Expressions, Uses of Regular Expressions.

4.4 Finite Automata and Regular Expressions:Properties of Regular Sets and Regular Languages, Arden’s Theorem

4.5 Equivalence of Finite Automata and Regular Expressions, Equivalence of DFA and Regular Expression, Equivalence of NFA and Regular Expression

###### UNIT V: TRANSDUCERS, CONTEXT-FREE GRAMMARS AND CONTEXT-FREE LANGUAGES AND SIMPLIFICATION OF CONTEXT – FREE GRAMMAR

5.1 Transducers: Moore Machine, Mealy Machine, Difference between Moore and Mealy Machines, Properties / Equivalence of Moore and Mealy Machines.

5.2 Context-Free Grammars and Context-Free Languages: Types of Grammar, Ambiguous and Unambiguous Grammars, Noam Chomsky’s Classification of Grammar and Finite Automata, Relation between Regular Grammar and Finite Automata

5.3 Simplification of Context – Free Grammar: Simplification of Context-Free Grammars, Elimination of Є -Productions

5.4 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

###### UNIT VI: TURING MACHINE AND TM EXTENSIONS AND LANGUAGES

6.1 Turing Machine: Introduction, Components of Turing Machine, Description of Turing Machine,

6.2 Elements of TM, Moves of a TM, Language accepted by a TM, Role of TM’s , Design of TM’s

6.3 TM Extensions and Languages: TM Languages, Undecidable Problem, P and NP Classes of Languages