Course Description

Automata theory (also known as Theory Of Computation) is a theoretical branch of Computer Science and Mathematics, which mainly deals with the logic of computation with respect to simple machines, referred to as automata. 

Automata* enables scientists to understand how machines compute the functions and solve problems. The main motivation behind developing Automata Theory was to develop methods to describe and analyze the dynamic behavior of discrete systems. 

Automata originated from the word “Automaton” which is closely related to “Automation”.

Course Prerequisites:  Knowledge about set Theory

•                                             Knowledge about Discrete mathematics

Course Objectives: This course (BCS503) will enable students to: 

• Introduce core concepts in Automata and Theory of Computation.

• Identify different Formal Language Classes and their Relationships.

• Learn concepts of Grammars and Recognizers for different formal languages.

• Prove or disprove theorems in automata theory using their properties.

• Determine the decidability and intractability of Computational problems. Trees. 

Course Outcomes: The student will be able to : 

• Apply the fundamentals of automata theory to write DFA, NFA, Epsilon-NFA and conversion between them.

•  Prove the properties of regular languages using regular expressions.

•  Design context-free grammars (CFGs) and pushdown automata (PDAs) for formal languages.

• Design Turing machines to solve the computational problems.

• Explain the concepts of decidability and undecidability.