STELLA MARIS COLLEGE (AUTONOMOUS), CHENNAI - 600 086

General Elective Course Offered by the department of Mathematics

to students of B A. / B.Sc. / B.V.A. / B.Com. /B.B.A. / B.S.W. Degree Programme

SYLLABUS

(Effective from the academic year 2019-2020)

AUTOMATA

CODE: 19MT/GE/AM22 CREDITS: 2

L T P: 2 0 0 TOTAL TEACHING HOURS: 26

OBJECTIVES OF THE COURSE

Ø To familiarize students with the foundations and principles of theory of computations

Ø To introduce an abstract model of a computer with an exposure to applications of Automata theory

COURSE LEARNING OUTCOMES

On successful completion of the course, students will be able to

Ø understand the connection between language and computations

Ø analyze the computational strength of machines

Ø recognize applications of Automaton

Unit 1 (10 Hours) Introduction to the Theory of Computation

1.1 Mathematical preliminaries and notations, Sets, Functions and Relations

1.2 Graphs and Trees, Proof Techniques

1.3 Three Basic Concepts

1.4 Languages, Grammars and Automata

1.5 Some Applications

Finite Automata

1.6 Deterministic Finite Accepters

1.7 Deterministic Accepters and Transition Graphs

1.8 Languages and Dfas, Regular Languages

1.9 Nondeterministic Finite Accepters, Definition of a NDA

1.10 Why Nondeterminism?

Unit 2 (8 Hours) Regular Languages and Regular Grammars

2.1 Regular Expressions

2.2 Languages Associated with RE

2.3 RE Denote RL , RE for RL

2.4 RG, Right- and Left-Linear Grammars

Context Free Languages

2.5 Context Free Grammar

2.6 Left Most and Right Most Derivations

Unit 3 (8 Hours)

Project

3.1 Application of Finite Automata and Formal Language

3.2 Design of Vending Machine

3.3 Document Language Design

3.4 Cryptography

3.5 DNA Computing

BOOK FOR STUDY

Peter Linz, An Introduction to Formal Languages and Automata, 3^rd Edition. New Delhi: Narosa Publishing House, 2005.

BOOKS FOR REFERENCE

Rani Siromoney, Formal Languages and Automata. Madras: The Christian Literature Society, 1974.

Behera, Nayak and Pallnayak, Formal Languages and Automata Theory. New Delhi: Vikas,

2014.

Kamala Krithivasan and Rama. R., Introduction to Formal Languages, Automata Theory and

Computation, Chennai: Pearson, 2009.

WEB RESOURCE

http://www.iitg.ernet.in/dgoswami/Flat-Notes.pdf

https://www.ics.uci.edu/~goodrich/teach/cs162/notes/

https://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/apps.html

http://www.sti.uniurb.it/aldini/publications/lfga.pdf

PATTERN OF ASSESSMENT: (Totally Internal)

Theory 20%; Problem 80%

Continuous Assessment Test: Total Marks: 25 marks Duration:40 minutes

Section A : 5 × 2 = 10 marks (Choose five from six questions)

Section B : 3 × 5 = 15 marks (Choose three from five questions)

Other Components: Total marks: 25

Quiz/Assignment/Problem Solving