Regular Language

o Regular language can be recognized by FSM

o DFSM and NFSM are equivalent, we will use “FSM” where convenient

Recall from FSM

Recall from FSM

Recall from FSM

Recall from FSM

Regular Expression: defines a regular language

⮚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

⮚Since the language recognized by an FSM is regular, it follows that a language is regular iff some regular expression describes it

这段内容阐述了正则表达式（Regular Expression）与有限状态机（Finite State Machine, FSM）之间的等价关系，以及它们与正则语言之间的联系。

1. 每一个正则表达式都等价于一个FSM： 正则表达式定义了一类语言，这类语言可以由有限状态机来识别。也就是说，对于每一个正则表达式，存在一个有限状态机可以识别由这个正则表达式描述的语言。
2. 对每一个正则表达式，都存在一个FSM可以识别它定义的语言： 这意味着正则表达式和FSM在表达语言方面是等价的。从正则表达式可以构建出一个FSM，使其能够识别该正则表达式所描述的所有字符串。
3. 反之亦然：对于每一个FSM，都存在一个正则表达式来定义FSM所识别的语言： 不仅是正则表达式可以被转化为FSM，反过来，对于每一个FSM，也都可以构造一个正则表达式，使其描述该FSM所能识别的语言。这说明FSM和正则表达式是双向的、等价的。
4. 因此，由FSM识别的语言是正则的，当且仅当有正则表达式描述它： 由于FSM识别的语言被称为“正则语言”，因此可以得出一个结论：如果某个语言可以被某个FSM识别，则它一定是正则语言。同样，如果某个语言可以用正则表达式来描述，那么它也是正则语言。

总的来说，这段内容强调了正则表达式和FSM在描述正则语言方面的等价性，正则语言可以用两种形式来描述：正则表达式和FSM，它们本质上描述的是同一类语言，即正则语言。