文档介绍：Formal Languages and Theory putation
Wen-Hsiang Tsai
蔡文祥講座教授
2010/9
Taj Mahal in India
1
Chapter 0
Introduction
Opera House in Sidney, Australia
2
Outline
Reasons for Taking This Course
General Concepts
Problems Studied in Theory putation
Fields Related to Theory putation
Applications of Theory putation
Brief History of Theory putation
Textbooks and Course Grading
3
Reasons for Taking This Course
Philosophy puter science (CS)
Indispensable plete study of CS
Broadening views in all fields of CS
Enhancing problem solving capability
Basic training for undergraduate students
Background course for graduate students
Qualification exam topic for Ph. D. students.
4
General Concepts
Course title ---
“Formal Languages and Theory putation”(正規語言與計算理論)
Scope of course:
Formal languages
Automata plexity
5
General Concepts
Formal Languages ---
Definition ---
Study of “strings of symbols,” including their
descriptions, properties,
generations, recognitions,
compiling, applications, …
6
General Concepts
Formal Languages ---
Concepts (1/2) ---
Strings of symbols include those of
natural languages,
computer languages,
discrete signals, …
7
General Concepts
Formal Languages ---
Concepts (2/2) ---
Results of study of automatic processing of symbolic information
Parallel to numerical mathematical processing
Similar to the role of set theory (集合論) in mathematics
8
General Concepts
Automata Theory ---
A question ---
Do you know how a vending machine works? Can you design one?
Vending machine room seen in Hokkaido, Japan 2004
9
General Concepts
Automata Theory ---
An example (1/3) ---
How to design a vending machine?
Use a finite automaton!
10