在读正则语言之前先明确一下语言、文法的基本概念。
一、基本概念
- 语言
首先给出一个有限的、非空的符号集合Σ，成为字母表。
字母表中任意字符组成的字符串就是一个句子，比如aaa，bbb，即Σ*的元素。
这些字符串构成的集合就是一个语言，比如{aaa,bbb}，即Σ*的子集。
举一个例子：
Σ={a，b}，则Σ*={ε，a，b，aa，ab，bb，aaa，bbb，...}，里面的每一个元素都是一个句子，集合{a，aa，bbb}就是Σ上的一个语言，因为它有有限个句子，所以称之为有限语言。集合L={aⁿbⁿ：n>=0}也是Σ上的语言，这个语言是无限的。
2. 文法
文法G是一个四元组G=（V,T,S,P）
V：变量 T：终结符 S：开始符，S∈T P：产生式
通过产生式可以知道文法是如何将一个字符串转化成另一个字符串的，形如X—>Y。
- 那文法是用来干什么的？
文法用来生成语言的。
比方说我们自然语言中句型有：
S+V
S+V+O
eg：He works very hard. He took your bag.
里面的S,V,O就相当于变量V，而句子中的字符串类似he,very就相当于终结符，P产生式就相当于句型。
V={S，V，O,...}
T={He,works,very,hard,...}
S=sentence
P={
sentence—>SVO
S—>He
V—>works
O—>hard
}
即，设G=（V,T,S,P）是一个文法，那么集合L(G)={w∈T*：S*=>w}就是该文法G生成的语言，S通过多步推导得到w，推导过程中变量和终结符构成的字符串为推导的句型，例如S—>aSb,其实这个推导过程是一个递归的过程，为了最终得到一个句子,需要S—>ε作为终止条件，最终推出aⁿbⁿ的句型。
- 当几个产生式有相同的左部时，则它们的右部可以写在同一个产生式的右边，中间用|隔开，例如S—>aSb|ε。