3_regular_expressions.md

1.3 Regular Expressions

定义1.52（regular expression）

regular expression可以理解成language之间的操作。

比如 $$(0\cup 1)$$\$$s^*$$

Say that $$R$$ is a regular expression if $$R$$ is

1. $$a$$，for $$a\in\Sigma$$,
2. $$\sigma$$,
3. $$\emptyset$$,
4. $$(R_1\cup R_2)$$, where $$R_1$$ and $$R_2$$ are regular expressions,
5. $$(R_1\cdot R_2)$$, where $$R_1$$ and $$R_2$$ are regular expressions, or
6. $$(R_1^*)$$, where $$R_1$$ is regular expressions,

虽然只有三个operation，但很多其他operations可以构造出来，比如$$R^+$$，补、交

定理（L(RE) = L(FA））

A language is regular if and only if some regular expression describes it

证明方法：引入GNFA来证明充分性，构造法证明必要性；

FA和RE有相同的表达能力