Outline & Core Concepts
Regular Language
Regular language can be recognized by FSM（有限状态机）
- DFSM and NFSM are equivalent, we will use "FSM" where convenient
Regular Expression 正则表达式
➢ Each regular expression is equivalent to an FSM
➢ For any regular expression, there exists an FSM that recognizes the language defined by the regular expression
➢ And vice versa: for any FSM, there exist a regular expression that defines the language recognized by the FSM
➢ 结论: a language is regular iff some regular expression describes it
Regular Languages = 可以被 FSM / 正则表达式 / 正则文法描述的语言
| 表达方式 | 作用 |
|---|---|
| FSM（自动机） | 判断字符串是否属于语言 |
| Regular Expression（正则表达式） | 描述语言 |
| Regular Grammar（正则文法） | 生成语言 |
Regular Operations 正则运算
- Union（并）: Choice among alternatives, indicated by
|or∪ - Concatenation（连接）: indicated by juxtaposition
○ - Repetition / Closure（闭包）: indicated by (Kleene star)
Precedence of Operations（运算优先级）
Highest: Repetition (*) Middle: Concatenation (○) Lowest: Union (∪)