FE-Logo
  • Home
  • Study Material
  • Computer Science and Engineering
    • Neural network and fuzzy systems
    • Cryptography
    • Software Engineering
    • Software project management
    • Data Structures Using c
    • Computer graphics
    • Mobile computing
    • Compiler design
    • Automata
    • Datamining and data ware housing
    • Artificial Intelligence
    • Operating System
    • Database Management Systems
    • Design and analysis of algorithms
    • Object oriented programming
    • Advanced Database Management System
    • Computer Organization and Architecture
    • Computer networks
    • Network management and securuty
    • Web Technology
    • Internet Fundamentals
    • Digital imge processing
    • Computer hardware
    • Graph Theory
    • Principals of Programming Language
    • Real Time Systems
    • Discrete Mathematics
    • Fundamental of Electronic Devices
    • Digital Electronics
    • Microprocessor and Interfacing
    • Data Communication and Networking
    • Professional Communication
    • Human Values and Professional Ethics
    • Basic Manufacturing Process
    • Physics-II
    • Physics-I
    • Computer Concept and C Programming
    • Environmental Engineering
    • Math -1
    • Math -2
    • Chemistry
    • Basic Electrical - First Year
    • Basic Electronics
    • Embedded System Design
    • Network Theory
    • Principle of Communication
    • Signal and Systems
    • Wireless Communication
    • Analog Electronics Circuits
    • Digital Signal processor
    • Numerical Analysis
    • Maths -3
    • Elements of Civil Engineering
    • Elements of Mechanical Engineering

  • Electronics and Communication Engineering
    • Wireless Communication
    • Satellite Communications
    • Optical Fiber Communication
    • Mobile communication
    • Radar and sonar engineering
    • Embedded system
    • Data Communication and Networking
    • Principle of Communication
    • TV ENGINEERING
    • Digital elecronics
    • Network theory
    • Electromagnetic Field Theory
    • Analog electronics
    • Antenna &Wave Propagation
    • Analog Electronic Circuits
    • Fundamentals of Electronics Devices
    • Microprocessors and Interfacing
    • Signals and Systems
    • Microwave Engineering
    • Advance Semiconductor Devices
    • Digital System Design
    • Mos ICs and Technology
    • Digital Signal Processing
    • Power Electronics
    • Numerical Methods
    • Control Systems - I
    • Math -3
    • Electrical Machines II (AC Machines)
    • Electrical Machines I (DC Machines)
    • Advance Control System
    • Electrical Drives
    • Professional Communication
    • Human Values and Professional Ethics
    • Basic Manufacturing Process
    • Physics-II
    • Physics-I
    • Computer Concepts and C programming
    • Environmental Engineering
    • Math-1
    • Math-2
    • Chemistry
    • Basic Electrical - First Year
    • Basic Electronics
    • Electronics Switching
    • Neural Network and Fuzzy Logics
    • Digital Image Processing
    • Data Structures Using C
    • Operating systems
    • Computer Organisation and Architecture
    • Network management and security
    • Object Oriented Programming
    • Electrical Instrumentation and Measurements
    • Digital communication
    • Electronic Measurements and Instrumentation
    • Elements of Civil Engineering
    • Elements of Mechanical Engineering
    • VLSI Design
    • Electronics Formula

  • Electrical and Electronics Engineering
    • Power system Analysis
    • Advance control system
    • Digital signal processing
    • Power Electronics
    • High Voltage Engineering
    • Electrical drives
    • Electrical Instrumentation And Process Control
    • Electrical Machines II (AC Machines)
    • Electrical Machines I (DC Machines)
    • Advanced Topics in Power Systems
    • Control system I
    • Switchgear and Protection
    • Element of Power System
    • Electrical Measurements and Measuring Instruments
    • Electrical Machine Design
    • Solid state devices
    • Numerical analysis
    • Electrical System Design and Estimation
    • Switched Mode Power Conversion
    • Non conventional energy resourses
    • Telemetry and Data Transmission
    • Utilization of Electrical Energy
    • Special Electrical Machines
    • Digital Electronics
    • Network Theory
    • Advanced Semiconductor Devices
    • Analog Electronics Circuits
    • Antena & Wave Propogation
    • Data Communication And Network
    • Electromagnetic Field Theory
    • Embedded System Design
    • Professional Communication
    • Human Values and Professional Ethics
    • Basic Manufacturing Process
    • Physics-II
    • Physics-I
    • Computer Concepts and C programming
    • Environmental Engineering
    • Math -1
    • Math -2
    • Engineering Chemistry
    • Basic Electrical - First Year
    • Basic Electronics
    • Fundamental of Electronic Devices
    • Microprocessors and Interfacing
    • Mobile Communication
    • Satellite Communications
    • Wireless Communication
    • Principle of Communication
    • Optical fiber communication
    • Computer Organisation
    • Database management system
    • Data mining and Data Warehousing
    • Data Structures Using C
    • Digital image processing
    • Software Engineering
    • Fluid Mechanics
    • Neural Networks and Fuzzy Logic
    • Hydraulic Machines
    • Operating System
    • Object Oriented Programming
    • Analog Electronics
    • Digital Communication
    • Mechatronics
    • Power Plant Engineering
    • Math -3
    • Elements of Civil Engineering
    • Elements of Mechanical Engineering

  • Mechanical Engineering
    • Computer Aided Manufacturing
    • Computer Aided Design
    • Six sigma
    • Operation research
    • Total quality management
    • Power Plant Engineering
    • Automobile Engineering
    • Avanced Welding Technology
    • Internal Combustion Engine
    • Machine Design I
    • Machine Design II
    • Heat And Mass Transfer
    • Theory Of Machines I
    • Theory Of Machines II
    • Material Science
    • Thermodynamics
    • Applied Thermodynamics
    • Refrigeration And Air-Conditioning
    • Strength Of Materials
    • Manufacturing Science I
    • Manufacturing Science II
    • Mechatronics
    • Industrial Engineering
    • Fluid Mechanics
    • Fluid Machinery
    • Electrical Machines
    • Measurement and Metrology
    • Professional Communication
    • Human Values and Professional Ethics
    • Basic Manufacturing Processes
    • Physics II
    • Physics I
    • Computer Concepts and C Programming
    • Environmental Engineering
    • Math -1
    • Math -2
    • Chemistry
    • Basic Electrical- First Year
    • Basic Electronics
    • Non Conventional Energy Resources
    • Unconventional Manufacturing Processes
    • Mechanical System Design
    • Quality Control
    • Maths 3
    • Elements of Civil Engineering
    • Elements Of Mechanical Engineering
    • Finite Element Method

  • Civil Engineering
    • Environmental Engineering-I
    • Engineering Geology
    • Geo informatics system
    • Fluid Mechanics
    • Water resources engineering
    • Construction Material
    • Surveying-I
    • Surveying - II
    • Transpoprtation Engineering
    • Design of Steel Structure
    • Hydraulic Machines
    • Soil Mechanics
    • Structure Analysis -1
    • Design of Concrete Structures-II
    • Design of Concrete Structures-II
    • Tunnel Engineering
    • Transportation Engineering 2/Railway Engineering
    • Structural Analysis -2
    • Environmental Engineering-II
    • Strength of Materials
    • Professional Communication
    • Human Values and Professional Ethics
    • Basic Manufacturing Process
    • Physics II
    • Physics I
    • Computer Concepts and C programming
    • Environmental engineering
    • Math -1
    • Math -2
    • Chemistry
    • Basic Electrical - First Year
    • Basic Electronics
    • Advanced Structural Design
    • Conctrete Technology
    • Principals of Town Planning and Architecture
    • Maths-3
    • Elements of Civil Engineering
    • Elements of mechanical engineering
    • Earthquake Resistant Desigm Of Building

  • First Year-Engineering Syllabus
    • Chemistry
    • Maths-1
    • Maths-2
    • Basic electrical - First Year
    • Basic Electronics
    • Elements Of Civil Engineering
    • Elements of Mechanical Engineering
    • Environmental Engineering
    • Computer concepts and c programming
    • Physics-I
    • Physics-II
    • Basic Manufacturing Process
    • Human Values and Professional Ethics
    • Professional Communication

Automata
  • Online Study
  • Computer Science and Engineering
  • Automata

This study material is classroom notes & handbook on Automata theory subject for Information technology (IT), Computer Science engineering, discrete mathematics & Mathematics students. It is part of engineering education which brings important topics, notes, news & blog on the subject. It covers 138 topics of Automata in detail. These 138 topics are divided into 5 units.

Introduction to Automata
  • Introduction to automata theory and Formal Languages
  • Finite automata
  • Deterministic finite state automaton (DFA)
  • Sets
  • Relations and Functions
  • Asymptotic Behavior of Functions
  • Grammar
  • Graphs
  • Languages
  • Nondeterministic finite automaton
  • Strings and Languages
  • Boolean Logic
  • Orders for Strings
  • Operations on languages
  • Kleene Star, ‘∗’
  • Homomorphism
  • Machines
  • The power of DFAs
  • Machine types that accept non-regular languages
  • Equivalence of NFA and DFA
  • Regular Expressions
  • Regular Expressions and Languages
  • Building Regular Expressions
  • NFAs to Regular Expression
  • Two-way Finite Automata
  • Finite Automata with Output
  • Properties of regular sets (Languages)
  • Pumping Lemma
  • Closure properties of regular languages
  • Myhill-Nerode Theorem-1
  • Exampleof Non Deterministic Finite Automata
  • Conversion of NFA to DFA
  • Mealy and moore Machine
  • Myhill-Nerode theorem
  • Decision algorithms
  • NFA with ε-moves
Context free languages & grammar
  • Introduction to Context-Free Grammars
  • Conversion of Left-linear Grammar into Right-Linear Grammar
  • Derivation Tree
  • Parsing
  • Ambiguity
  • Simplification of CFG
  • Normal Forms
  • Greibach Normal Form
  • Pushdown Automata
  • Transition Functions for NPDA
  • Execution of NPDA
  • Relation between pda and context free language
  • CFG to NPDA
  • NPDA to CFG
  • Properties of context-free languages
  • Proof of Pumping Lemma
  • Usage of Pumping Lemma
  • dicision Algorithms
  • Binary Relation Basics
  • Transitive, and Related Notions
  • Equivalence (Preorder plus Symmetry)
  • The Power Relation between Machines
  • Error-correcting DFAs
  • Ultimate Periodicity and DFAs
  • A Taxonomy of Formal Languages and Machines
  • Introduction to Push-down Automata
  • Right- and Left-Linear CFGs
  • Developing CFGs
  • A Pumping Lemma for CFLs
  • A Pumping Lemma for CFLs
Fixed point logic Unit
  • Dealing with Recursion
  • The Y operator
  • The least fixed-point
  • The Automaton/Logic Connection
  • Binary Decision Diagrams (BDDs)
  • Basic Operations on BDDs
  • Stabilization at a Fixed-Point
Automata and Logic
  • Context sensitive grammar and languages
  • The chomsky hirarchy
  • Unrestricted grammar
  • Introduction to Complexity Theory
  • polynomial time algorithm
  • boolean satisfiablity
  • Additional NP problem
  • Formal systems
  • Composition and recursion
  • Ackermann's theorem
  • Propositions
  • Connectives
  • Tautology, Contradiction and Contingency
  • Logical Identities
  • Logical inference
  • Predicates and quantifiers
  • Quantifiers and logical operators
  • Normal forms
Temporal logic
  • Turing Machine
  • Programming a Turing Machine
  • Turing Machines as Transducers
  • Complete language and functions
  • Modification of turing machines
  • Church-turing thesis
  • Enumerating Strings in a Language
  • Halting Problem
  • Rice's Theorem
  • Acceptance, Halting, Rejection
  • NDTMs
  • Simulations of turing machine
  • Basic Undecidability Proofs
  • Rice’s Theorem
  • Greibach’s Theorem
  • Post’s correspondence problem (PCP)
  • PCP is undecidable
  • Proof sketch of the undecidability of PCP
  • Basic Notions in Logic including SAT
  • Axiomatization of Propositional Logic
  • First-order Logic (FOL) and Validity
  • Examples of interpretations
  • Validity of first-order logic is undecidable
  • Properties of Boolean Formulas
  • Overview of direct DNF to CNF conversion
  • CNF-conversion using gates
  • DIMACS file encoding
  • Unsatisfiable CNF instances
  • 3-CNF, =-satisfiability, and general CNF
  • 2-CNF satisfiability
  • DFA for Presburger Arithmetic
  • Presburger Formulas and DFAs
  • Encoding conventions
  • Conversion algorithm: Presburger formulas to automata
  • Pitfalls to Avoid
  • An Introduction to Model Checking
  • Reactive Computing Systems
  • Model checking vs. testing
  • Buchi automata, and Verifying Safety and Liveness
  • Dining Philosophers
  • Model (proctype) and property (never) automata
  • Temporal Logics
  • Computations vs. computation trees
  • Temporal formulas are Kripke structure classifiers
  • LTL vs. CTL through an example
  • LTL syntax
  • CTL syntax