Automata Theory and Formal Languages

NTNU 自動機理論與正規語言

Back to Note Overview

tags: AutomataTheoryandFormalLanguages 110-1 選修 CSIE NTNU

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

• Why study theory
• Mathematical preliminaries ans notation
• What is automation
• What is formal language
• What is algorithm

Ch.02 Finite automata

• Deterministic finite accepters
• Nondeterministic finite accepters
• Equivalence of deterministic and nondeterministic finite accepters

Ch.03 Regular languages and regular grammars

• Two alternative methods for representing regular languages, such as regular expressions and regular grammars

Ch.04 Properties of regular languages

• 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