JNTUK B.Tech Formal Languages & Automata Theory gives you detail information of Formal Languages & Automata R13 syllabus It will be help full to understand you complete curriculum of the year.
Objectives: Understanding of programming language construct, how input is converted into output from the machine hardware level
UNIT I
- Objectives: Analysis of Finite state machine, its representation and automata
- Fundamentals of Automata– Computation, Finite State Machine, Components of Finite State Automata, Elements of Finite State System ,Mathematical representation of Finite State Machine, Automata Classification, Automata in Real World
UNIT II
- Objectives: Delineation of various components of formal languages and grammars.
- Formal Language Theory– Symbols, Alphabets and Strings, Operations on Strings, Formal Languages, Operations on Languages, Formal Languages/ Grammar Hierarchy: Formal Languages, Regular Language, Context-Free Language, Context-Sensitive Language, Recursive Language, Recursively Enumerable Language, Other Forms of Formal Languages, Relationship between Grammars and Languages
UNIT III
- Objectives: Description of finite automata, variants in it and their equivalence
- 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
- Equivalent Automata: Equivalent Finite-State Automata, Equivalence of NFA/NFA- ɛ and DFA, Equivalence of NFA, with Є moves to NFA, without Є – moves.
UNIT IV
- Objectives: Minimization, optimization of finite automata, regular expressions and equivalence of finite automata and regular expressions.
- Minimization/ Optimization of DFA: Optimum DFA, Minimal DFA, Two way DFA, DFA Vs 2DFA Regular Expressions and Languages:Regular languages, Regular expressions, Components of Regular Expression, Properties of Regular Expressions, Uses of Regular Expressions. Finite Automata and Regular Expressions:Properties of Regular Sets and Regular Languages, Arden’s
Theorem, Equivalence of Finite Automata and Regular Expressions, Equivalence of DFA and Regular Expression, Equivalence of NFA and Regular Expression
UNIT V
- Objectives: Illustration about grammars, classification and simplification of grammaers
- Transducers: Moore Machine, Mealy Machine, Difference between Moore and Mealy Machines, Properties / Equivalence of Moore and Mealy Machines. 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. Simplification of Context – Free Grammar: Simplification of Context-Free Grammars, Elimination of Є – Productions, 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
- Objectives: Delineation of turing machines
- 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 TM Extensions and Languages: TM Languages, Undecidable Problem, P and NP Classes of Languages.
Text Books
- A Text Book on Automata Theory, Nasir S.F.B, P.K. Srimani, Cambridge university Press
- Introduction to Automata Theory, Formal languages and computation, Shamalendu kandar, Pearson
- Elements of Theory of Compuation, Harry R Lewis, Papdimitriou, PHI
- Introduction to theory of computation, 2nd ed, Michel sipser, CENGAGE
Reference Books
- Formal Languages and automata theory, C.K. Nagpal, OXFORD
- Theory of Computation , aproblem solving approach, kavi Mahesh, Wiley
- Automata, computability and complexity, Theory and applications, Elaine rich, PEARSON
- Theory of Computation, Vivek kulkarni, OXFORD
For more information about all JNTU updates please stay connected to us on FB and don’t hesitate to ask any questions in the comment.