Formal Languages and Automata Theory (CS 302)

2025 Fall
Faculty of Engineering and Natural Sciences
Computer Sci.& Eng.(CS)
3
6
Kemal İnan inan@sabanciuniv.edu,
Click here to view.
English
Undergraduate
--
Formal lecture,Interactive lecture
Interactive,Learner centered,Communicative
Click here to view.
Programs\Type Required Core Elective Area Elective
Computer Science and Engineering *
Computer Science and Engineering *
Electronics Engineering *
Electronics Engineering *
Materials Science and Nano Engineering *
Materials Science and Nano Engineering (Previous Name: Materials Science and Engineering) *
Mechatronics Engineering *
Mechatronics Engineering *
Microelectronics *
Telecommunications *

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 OUTCOMES

  • 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

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; have the ability to continue to educate him/herself. 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

1. Possess sufficient knowledge of mathematics, science, fundamental engineering, computational methods 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 while considering the UN Sustainable Development Goals; choose and apply suitable analysis, design, estimation/prediction 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; use information technologies effectively. 3

4. Have the ability to design a complex system, process, instrument or a product under realistic constraints and conditions, with the goal of fulfilling creative current and future requirements. 2

5. Use research methods, including conducting literature reviews, designing experiments, performing experiments, collecting data, analyzing results, and interpreting results, to investigate complex engineering problems or discipline-specific research topics. 2

6. Possess knowledge of business practices such as project management, risk management, change management, and economic feasibility analysis; awareness on entrepreneurship and innovation. 3

7. Possess knowledge of impact of engineering solutions on society, health and safety, the economy, sustainability, and the environment within the framework of the UN Sustainable Development Goals; awareness on legal outcomes of engineering solutions; awareness of acting impartially and inclusively without any form of discrimination; act in accordance with ethical principles, possessing knowledge of professional and ethical responsibilities. 2

8. Communicate effectively, both orally and in writing, on technical subjects, considering the diverse characteristics of the target audience (such as education, language, and profession). 2

ASSESSMENT METHODS and CRITERIA

  Percentage (%)
Final 35
Midterm 20
Quiz 35
Assignment 10

RECOMENDED or REQUIRED READINGS

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)