AN INTRODUCTION to FORMAL LANG. and AUTO. THEORY

AIM

This course aims to introduce concepts in Automata theory. Based on topics on identifying the different formal language classes, their relationship and diffrences. Students are supposed to design theoretic machines for specific purposes, and prove/disprove properties of these machines.

CONTENT

This course contains; Course Info, Introduction to Finite State Automata ,Deterministic and Nondeterministic Finite State Automata ,Equivalence of deterministic and nondeterministic Automata ,Regular Expression and Equivalence with Non-deterministic Automata ,Algebraic Laws for Regular Expression,Pumping Lemma for Regular Languages and Minimization of finite state automata ,Context Free Grammars ,Context Free Languages ,Parse Trees and Ambiguity of grammar ,Pushdown Automata ,Chomsky Normal Form ,Pumping Lemma for Context Free languages ,Turing Machines ,Basic Calculation with Turing machines.

1. 1

   Identify different classes of languages and design automaton to accept that language

   Taught by: Discussion Method, Demonstration Method, Problem Solving Method, Self Study Method, Question - Answer Technique, Problem Baded Learning Model, Inquiry-Based Learning, Experiential Learning, Lecture Method · Assessed by: Traditional Written Exam, Quiz

2. 2

   Prove or disprove if the given language is regular, proving equivalence of different automata

   Taught by: Discussion Method, Demonstration Method, Problem Solving Method, Self Study Method, Question - Answer Technique, Problem Baded Learning Model, Inquiry-Based Learning, Experiential Learning, Lecture Method · Assessed by: Traditional Written Exam, Quiz

3. 3

   Represent a given language by a context-free grammar, removing ambiguity, and simplification of a given grammar.

   Taught by: Discussion Method, Demonstration Method, Problem Solving Method, Self Study Method, Question - Answer Technique, Problem Baded Learning Model, Inquiry-Based Learning, Experiential Learning, Lecture Method · Assessed by: Traditional Written Exam, Quiz

4. 4

   Desing a Turing machine for a certain purpose.

   Taught by: Discussion Method, Demonstration Method, Problem Solving Method, Self Study Method, Question - Answer Technique, Brainstorming Technique, Problem Baded Learning Model, Inquiry-Based Learning, Experiential Learning, Lecture Method · Assessed by: Traditional Written Exam, Quiz

WEEKLY PLAN

1. WEEK 1

   Course Info, Introduction to Finite State Automata

   Preparation: Textbook Chapter 1

2. WEEK 2

   Deterministic and Nondeterministic Finite State Automata

   Preparation: Textbook Chapter 2.1-2.3

3. WEEK 3

   Equivalence of deterministic and nondeterministic Automata

   Preparation: Textbook Chapter 2.3

4. WEEK 4

   Regular Expression and Equivalence with Non-deterministic Automata

   Preparation: Textbook Chapter 3

5. WEEK 5

   Algebraic Laws for Regular Expression

   Preparation: Textbook Chapter 4.2

6. WEEK 6

   Pumping Lemma for Regular Languages and Minimization of finite state automata

   Preparation: Textbook Chapter 4.1

7. WEEK 7

   Context Free Grammars

   Preparation: Textbook Chapter 5.1

8. WEEK 8

   Context Free Languages

   Preparation: Textbook Chapter 5.1, 5.4

9. WEEK 9

   Parse Trees and Ambiguity of grammar

   Preparation: Textbook Chapter 5.4

10. WEEK 10

    Pushdown Automata

    Preparation: Textbook Chapter 6

11. WEEK 11

    Chomsky Normal Form

    Preparation: Textbook Chapter 7.1

12. WEEK 12

    Pumping Lemma for Context Free languages

    Preparation: Textbook Chapter 7.2

13. WEEK 13

    Turing Machines

    Preparation: Textbook Chapter 8.1

14. WEEK 14

    Basic Calculation with Turing machines

    Preparation: Textbook Chapter 8.1,8.2

ASSESSMENT

• Rate of Midterm Exam to Success30%
• Rate of Final Exam to Success70%

WORKLOAD

READING

• Lecture notes will be supplied by instructor but following textbooks could be used as supplementary materials. 1. J. Hopcroft, R. Motwani, and J. Ullman. Introduction to Automata Theory, Languages, and Computation, 3rd edition, 2007, Pearson/Addison-Wesley, 2. Theory of Automata By C.J. Martin

TEACHING STAFF

• Assist.Prof. Cihan Bilge GÜRBÜZCOORDINATOR
• Assist.Prof. Cihan Bilge GÜRBÜZ