Automata Theory and Formal Languages
opinarer@gsu.edu.tr
Content
Objective
Learn the basics of language theory
Introduce the basics of computability, decidability and complexity.
Course Content
• Mathematical Review and Formal Foundations
• Deterministic Finite Automata (DFA)
• Nondeterministic Finite Automata (NFA)
• Regular Expressions and Kleene's Theorem
• Properties of Regular Languages
• Pumping Lemma for Regular Languages
• Minimization of Automata
• Context-Free Grammars (CFG)
• Pushdown Automata (PDA)
• Properties of Context-Free Languages
• Normalizations
• Turing Machines
• Undecidability
• Introduction to Complexity
Course Learning Outcomes
- Familiarization with theoretical computer science
- Acquisition of key concepts and theorem of the theory of language
- Acquisition of problems related to the notions of computability and decidability.
Teaching and Learning Methods
Use of slideshow during the class and available online. Exercises applications during each class.
References
- Introduction to Automata, Theory, Languages and Computation, J.E. Hopcroft, Jeffrey D. Ullman, Rajeev Motwan, Addison Wesley
- Logique(s), langages formels et complexité pour l'informatique, Narendra Jussien, Hermes
- Elements of Automata Theory, Jacques Sakarovitch , Cambridge University Press
Weekly Contents
| Week | Weekly Contents |
|---|---|
| 1 | Mathematical Review and Formal Foundations |
| 2 | Deterministic Finite Automata (DFA) |
| 3 | Nondeterministic Finite Automata (NFA) |
| 4 | Regular Expressions and Kleene's Theorem |
| 5 | Properties of Regular Languages |
| 6 | Pumping Lemma for Regular Languages |
| 7 | Minimization of Automata |
| 8 | Mid Term |
| 9 | Context-Free Grammars (CFG) |
| 10 | Pushdown Automata (PDA) |
| 11 | Properties of Context-Free Languages |
| 12 | Normalizations |
| 13 | Turing Machines |
| 14 | Undecidability |
Assessment System
| Activities | Number | Contribution |
|---|---|---|
| Contribution of in-term studies to overall grade | 1 | 50 |
| Contribution of final exam to overall grade | 1 | 50 |
| Total | 2 | 100 |
| Activities | Number | Contribution |
|---|---|---|
| Assignments | 0 | 0 |
| Presentation | 0 | 0 |
| Midterm Examinations (including preparation) | 1 | 50 |
| Project | 0 | 0 |
| Laboratory | 0 | 0 |
| Other Applications | 0 | 0 |
| Quiz | 0 | 0 |
| Term Paper/ Project | 0 | 0 |
| Portfolio Study | 0 | 0 |
| Reports | 0 | 0 |
| Learning Diary | 0 | 0 |
| Thesis/ Project | 0 | 0 |
| Seminar | 0 | 0 |
| Other | 0 | 0 |
| Make-up | 0 | 0 |
| Total | 1 | 50 |
Relation of Proficiency
| No | Program Learning Outcomes | Contribution | ||||
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | Matematik, fizik ve mühendislik bilimlerine özgü konularda yeterli bilgi birikimi; bu alanlardaki kuramsal ve uygulamalı bilgileri, mühendislik problemlerinin modellenmesi ve çözümünde kullanabilme becerisi. | |||||
| 2 | Karmaşık bilgisayar mühendisliği problemlerini saptama, tanımlama, formüle etme ve çözme becerisi; bu amaçla uygun analiz ve modelleme yöntemlerini seçme ve uygulama becerisi. | X | ||||
| 3 | Yazılımsal veya donanımsal karmaşık bir sistemi, süreci veya donanımı gerçekçi kısıtlar ve koşullar altında, belirli gereksinimleri karşılayacak şekilde tasarlama becerisi; bu amaçla modern tasarım yöntemlerini uygulama becerisi. | |||||
| 4 | Mühendislik uygulamalarında karşılaşılan karmaşık problemlerin analizi ve çözümü için gerekli olan modern teknik ve araçları geliştirme, seçme ve kullanma becerisi; bilişim teknolojilerini etkin bir şekilde kullanma becerisi. | X | ||||
| 5 | Analitik düşünce ile bir sistemi, sistem bileşenini ya da süreci analiz etme, modelleme, deney tasarlama ve yapma, veri toplama, çözüm algoritmaları üretebilme, uygulamaya alma ve geliştirme becerileri. | |||||
| 6 | Disiplin içi ve çok disiplinli takımlarda etkin biçimde çalışabilme becerisi; bireysel çalışma becerisi. | |||||
| 7 | Türkçe sözlü ve yazılı etkin iletişim kurma becerisi; en az iki yabancı dil bilgisi; etkin rapor yazma ve yazılı raporları anlama, yazılım ve donanım tasarımını, gerekirse teknik resim metotları kullanarak raporlayabilme, etkin sunum yapabilme becerisi. | |||||
| 8 | Bilgiye erişebilme ve bu amaçla kaynak araştırması yapabilme, veri tabanları ve diğer bilgi kaynaklarını kullanabilme becerisi | |||||
| 9 | Yaşam boyu öğrenmenin gerekliliği bilinci; kendini sürekli yenileme becerisi. | |||||
| 10 | Mesleki etik ilkelerine uygun davranma, mesleki sorumluluk bilinci; mühendislik uygulamalarında kullanılan standartlar hakkında bilgi. | |||||
| 11 | Proje yönetimi, risk yönetimi ve değişiklik yönetimi gibi, iş hayatındaki uygulamalar hakkında bilgi; girişimcilik, yenilikçilik hakkında farkındalık; sürdürülebilir kalkınma hakkında bilgi. | |||||
ECTS
| Activities | Number | Period | Total Workload |
|---|---|---|---|
| Class Hours | 14 | 3 | 42 |
| Working Hours out of Class | 14 | 2 | 28 |
| Assignments | 0 | 0 | 0 |
| Presentation | 0 | 0 | 0 |
| Midterm Examinations (including preparation) | 1 | 10 | 10 |
| Project | 0 | 0 | 0 |
| Laboratory | 0 | 0 | 0 |
| Other Applications | 0 | 0 | 0 |
| Final Examinations (including preparation) | 1 | 12 | 12 |
| Quiz | 0 | 0 | 0 |
| Term Paper/ Project | 0 | 0 | 0 |
| Portfolio Study | 0 | 0 | 0 |
| Reports | 0 | 0 | 0 |
| Learning Diary | 0 | 0 | 0 |
| Thesis/ Project | 0 | 0 | 0 |
| Seminar | 0 | 0 | 0 |
| Other | 0 | 0 | 0 |
| Make-up | 0 | 0 | 0 |
| Yıl Sonu | 0 | 0 | 0 |
| Hazırlık Yıl Sonu | 0 | 0 | 0 |
| Hazırlık Bütünleme | 0 | 0 | 0 |
| Total Workload | 92 | ||
| Total Workload / 25 | 3.68 | ||
| Credits ECTS | 4 | ||