# Automata Theory and Formal Languages
NTNU 自動機理論與正規語言
##### [Back to Note Overview](https://hackmd.io/@NTNUCSIE112/NTNUNote)

{%hackmd @sophie8909/pink_theme %}
###### tags: `AutomataTheoryandFormalLanguages` `110-1` `選修` `CSIE` `NTNU`
<!-- tag順序 [課程] [學期][系 必選] or [學程 學程名(不含學程的 e.g. 大師創業)][學校] -->
<!-- 記得加到 Note Overview -->
##### Textbook: An Introduction to Formal Languages and Automata, 6th edition, by Peter Linz. Jones and Bartlett Inc., 2017, 開發圖書
## Score
- Midterm 25%-40%
- 11/16
- Range:
- Final 25%-40%
- 01/11
- Homework 20%-35%
- 題目在課本都有解答
- HW1(10/19)
- Deadline: 10/26
- range: ch.1 - ch.3
- HW2(12/7)
- Deadline: 12/14
## Outline
1. Finite Automata
- formal language
2. Pushdown Automata
- Conotext-Free languages
3. Turing Machine
### [Ch.01 Introduction to the theory of computation](https://hackmd.io/@NTNUCSIE112/AT110-1_1)
- Why study theory
- Mathematical preliminaries ans notation
- What is automation
- What is formal language
- What is algorithm
### [Ch.02 Finite automata](https://hackmd.io/@NTNUCSIE112/AT110-1_2)
- Deterministic finite accepters
- Nondeterministic finite accepters
- Equivalence of deterministic and nondeterministic finite accepters
### [Ch.03 Regular languages and regular grammars](https://hackmd.io/@NTNUCSIE112/AT110-1_3)
- Two alternative methods for representing regular languages, such as regular expressions and regular grammars
### [Ch.04 Properties of regular languages](https://hackmd.io/@NTNUCSIE112/AT110-1_4)
- Closure properties
- Elementary questions about regular languages, such as membership questions.
#### Identifying nonregular languages
### Ch.05 Conotext-Free languages (CFL)
- Define context-free grammars and languages
- Parsing: describe sentence structures
- Ambiguity（歧異性）: for understanding the meaning of sentence
- Context-free grammars and programming languages
### Ch.06 Simplification of context-free grammars and normal forms
- Study several transformations ans substitution because in many instances, it is desirable to place even more stringent restrictions on the grammars
- Investigate normal forms for context-free grammars
### Ch.07 Pushdown automata (PdA)
- Because finite automata cannot recognize all context-free languages, we introduce a new class of automata, i.e., pushdown automata
- Nondeterministic pushdown automata
- accept exactly context-free languages
- Deterministic pushdown automata
- accept deterministic context-free languages
### Ch.08 Properties of context-free languages
- The family of context-free languages occupies a central position in a hierarchy of formal languages
- To study the relationship between language families and to exhibit their similarities and differences, we investigate the characteristic properties of the various families
- Closure properties
- Decision algorithm for context-free languages
### Ch.09 Turing machine
Turing machine ↔ modern computers
- Want to discover even more powerful language families if we give the automation **more flexible storage**
- Standard Turing machine
- Combing Turing machines for complicated tasks
- Turing's thesis
<!-- 預計學期進度到這 -->
<!-- ### Ch.10
### Ch.11 -->