INT201 W4
This’s the note of INT201 Week4.
This week will focus on 正则语言的性质.
Lecture
Two characterisations of regular languages
A “regular language” means a language that can be defined using a regular expression. “正则语言”是指可以使用正则表达式定义的语言。
Kleene’s theorem
Regular languages are those languages that can be accepted by finite automata. 正则语言是可以被有限自动机接受的语言。
任何NFA都有一个等价的DFA。因此，当我们讨论有限自动机可以接受的语言时，我们不需要指定我们讨论的是DFA还是NFA。我们通过展示如何从NFA转换成正则表达式，反之亦然来证明Kleene's theorem。
如何将正则表达式改编成NFA
Recall how r.e’s are defined. To show that any r.e. has an equivalent NFA:
- Construct a NFA that accepts any single one-letter word
- Given two NFAs, construct a new one that accepts the concatenation of their languages
- Given two NFAs, construct a new one that accepts the union of their languages
- Given any single NFA, construct a new one that accepts the closure of its language
Cliam 1
Let L1 and L2 be languages over an alphabet A. If there are finite automata accepting L1 and L2 then there is a finite automaton accepting L1L2. 假设L1和L2是A之上的语言，如果有有限自动机接受L1和L2，那么也有一个有限自动机接受L1L2。
Proof:
Claim 2
Let L1 and L2 be languages over an alphabet A. If there are finite automata accepting L1 and L2 then there is a finite automaton accepting L1 ∪ L2. 假设L1和L2是字母表a上的语言，如果有接受L1和L2的有限自动机，那么就有接受L1∪L2的有限自动机。
Example:
Proof:
The 2 constructions so far give a general way of constructing a finite automaton that accepts any finite language. A word in a finite language is built from a sequence of concatenations The language is built from a sequence of unions of sets of words.
到目前为止，这两种构造给出了构造接受任何有限语言的有限自动机的一般方法。有限语言中的一个词是由一系列的连接词组成的。
Claim 3
If language L is accepted by some finite automaton, then so is language L*. 如果语言L被某些有限自动机接受，那么语言L*也被接受。
Proof:
References
- XJTLU INT201 Week4 slides