Click to Print This Page
Code CS 302
Term 201701
Title Formal Languages and Automata Theory
Faculty Faculty of Engineering and Natural Sciences
Subject Computer Sci.& Eng.(CS)
SU Credit 3
ECTS Credit 6.00 / 6.00 ECTS (for students admitted in the 2013-14 Academic Year or following years)
Instructor(s) Kemal ?nan inan@sabanciuniv.edu,
Detailed Syllabus
Language of Instruction English
Level of Course Undergraduate
Type of Course Click here to view.
Prerequisites
(only for SU students)
--
Mode of Delivery Formal lecture,Interactive lecture
Planned Learning Activities Interactive,Learner centered,Communicative
Content

Introduction to languages, grammars and computation, Chomsky hierarchy, Regular languages and regular expressions, finite state automata and nondeterminism, automata determinization and minimization, pumping lemma and closure properties for regular languages, context free languages and grammars, push- down automata, pumping lemma for context-free languages, closure properties of context-free languages.

Objective

To introduce finite state machines , contex free grammars and Turing Machines (only on an introductory level) and their properties as the basis for the formal expressivity of computer languages and present algorithms and their computational complexity for solving linguistic decision problems .

Learning Outcome

Construct deterministic and nondeterministic finite state automata (DFA and NFA) for solving simple decision problems and perform conversions from nondeterministic to deterministic finite automata as well as between regular expressions and finite state automata.

Evaluate the computational complexity of algorithms involved in the decision problems of finite state automata, use the pumping lemma to demonstrate the non-regularity of languages
Compute the minimal state machine corresponding to a DFA,
Understand and construct context-free grammars (CFG) for formal definitions involving recursion such as regular expressions ; in particular understand the fundamental role played by CFG in designing formal computer languages with simple examples
Construct (infinite state) push down automata as acceptors of context free languages ; in particular compute from CFGs the corresponding push down automaton and vice versa
Use the CFG version of the pumping lemma to prove languages that are not context free
Evaluate the computational complexity of algorithms involved in the decision problems of context free grammars and push down automaton, classify and simplify grammars into their useful canonical forms
Use deterministic push down automata to parse formal language strings (computer programs) by using (i) top down or (ii) bottom up techniques
Formulate simple language manipulation techniques using Turing Machines
In general ,learn and master the use mathematical induction techniques in proving statements on formal language and automata theory

Programme Outcomes
 
Common Outcomes For All Programs
1 Understand the world, their country, their society, as well as themselves and have awareness of ethical problems, social rights, values and responsibility to the self and to others. 1
2 Understand different disciplines from natural and social sciences to mathematics and art, and develop interdisciplinary approaches in thinking and practice. 1
3 Think critically, follow innovations and developments in science and technology, demonstrate personal and organizational entrepreneurship and engage in life-long learning in various subjects. 1
4 Communicate effectively in Turkish and English by oral, written, graphical and technological means. 3
5 Take individual and team responsibility, function effectively and respectively as an individual and a member or a leader of a team; and have the skills to work effectively in multi-disciplinary teams. 1
Common Outcomes ForFaculty of Eng. & Natural Sci.
1 Possess sufficient knowledge of mathematics, science and program-specific engineering topics; use theoretical and applied knowledge of these areas in complex engineering problems. 4
2 Identify, define, formulate and solve complex engineering problems; choose and apply suitable analysis and modeling methods for this purpose. 4
3 Develop, choose and use modern techniques and tools that are needed for analysis and solution of complex problems faced in engineering applications; possess knowledge of standards used in engineering applications; use information technologies effectively. 3
4 Ability to design a complex system, process, instrument or a product under realistic constraints and conditions, with the goal of fulfilling specified needs; apply modern design techniques for this purpose. 2
5 Design and conduct experiments, collect data, analyze and interpret the results to investigate complex engineering problems or program-specific research areas. 2
6 Knowledge of business practices such as project management, risk management and change management; awareness on innovation; knowledge of sustainable development. 3
7 Knowledge of impact of engineering solutions in a global, economic, environmental, health and societal context; knowledge of contemporary issues; awareness on legal outcomes of engineering solutions; understanding of professional and ethical responsibility. 2
Computer Science and Engineering Program Outcomes Core Electives
1 Design, implement, test, and evaluate a computer system, component, or algorithm to meet desired needs and to solve a computational problem. 5
2 Demonstrate knowledge of discrete mathematics and data structures. 5
3 Demonstrate knowledge of probability and statistics, including applications appropriate to computer science and engineering. 2
Materials Science and Nano Engineering Program Outcomes Area Electives
1 Applying fundamental and advanced knowledge of natural sciences as well as engineering principles to develop and design new materials and establish the relation between internal structure and physical properties using experimental, computational and theoretical tools. 1
2 Merging the existing knowledge on physical properties, design limits and fabrication methods in materials selection for a particular application or to resolve material performance related problems. 1
3 Predicting and understanding the behavior of a material under use in a specific environment knowing the internal structure or vice versa. 1
Mechatronics Engineering Program Outcomes Area Electives
1 Familiarity with concepts in statistics and optimization, knowledge in basic differential and integral calculus, linear algebra, differential equations, complex variables, multi-variable calculus, as well as physics and computer science, and ability to use this knowledge in modeling, design and analysis of complex dynamical systems containing hardware and software components. 4
2 Ability to work in design, implementation and integration of engineering applications, such as electronic, mechanical, electromechanical, control and computer systems that contain software and hardware components, including sensors, actuators and controllers. 3
Electronics Engineering Program Outcomes Area Electives
1 Use mathematics (including derivative and integral calculations, probability and statistics), basic sciences, computer and programming, and electronics engineering knowledge to design and analyze complex electronic circuits, instruments, software and electronics systems with hardware/software. 4
2 Analyze and design communication networks and systems, signal processing algorithms or software using advanced knowledge on differential equations, linear algebra, complex variables and discrete mathematics. 3
Assessment Methods and Criteria
  Percentage (%)
Final 30
Midterm 20
Exam 40
Assignment 10
Recommended or Required Reading
Textbook

MAIN TEXT: Introduction to Automata Theory, Languages and Computation , Hopcroft, Motwani & Ullman, Pearson (Addison Wesley) 2006 , 3rd edition

Readings

AUXILIARY TEXT : Elements of the Theory of Computation, Lewis & Papadimitrious, Prentice Hall 1998 (out of print and discontinued)