一、先简单介绍一下形式语言基本知识
1、字母表:符号的非空有限集合称为字母表
2、符号串:由某一字母表中的符号组成的有限符号序列称为该字母表的符号串
二、非形式化的语言:
①语言L和M的合并,LUM={s|s∈L或 s∈M}
②语言L和M的连接,LM={st|s∈L,t∈M}
③语言L的Kleene闭包,L*=
④语言L的正闭包,L+=
解释:
前面①,②都很好理解,关于③和④,这里说明一下。
③:
集合 L 的第 i 次幂是集合 L 同自身的 i 次串接的简写。即,Li 可以被理解成由 L 中的符号形成的所有长度为 i 的字符串的集合。
L = {"ab", "c"}
L0 = {ε}
L1 = { "c"}(由L中符号形成的所有长度为1的字符串的集合)
L2 ={"ab"} ,{"cc"}(由L中符号形成的所有长度为2的字符串的集合)等等
由此,Kleene 星号应用于字符串集合的例子:
L* = {"ab", "c"}* =
={ε}∪{ "c"}∪{"ab"} ∪{"cc"}∪{"abc"} ∪{"cab"}∪{"ccc"}∪{"abcc"}∪{"abab"}∪{"cabc"}∪{ "ccab"}∪{"ababc"}∪{"abcab"}∪{"cabab"}∪{"ababab"}∪……}
={ε, "c", "ab","cc", "abc","cab", "ccc","abab", "cabc", "ccab", "abcc", "ababc", "abcab","cabab", "ababab",……}
同理,Kleene 星号应用于字符集合的例子:
{'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}
④:
和③类似,只不过④中没有 L0 = {ε}
更多参见:http://zh.wikipedia.org/wiki/Kleene%E9%97%AD%E5%8C%85
三、文法(Grammar):
G={VT,VN,S,P}
VT是一个非空有限的符号集合,它的每个元素称为终结符号(Terminal)
VN是一个非空有限的符号集合,它的每个元素称为非终结符号(Non-Terminal)
S∈VN,称为文法G的开始符号
P是一个非空有限集合,它的元素称为产生式。
VT∩VN=∅
产生式,其形式为α→β,α称为产生式的左部,β称为产生式的右部,符号“→”表示“定义为”,并且α、β∈(VT∪VN) *,α≠ε,即α、β是由终结符和非终结符组成的符号串。
开始符S必须至少在某一产生式的左部出现一次。
另外可以对形式α→β,α→γ的产生式缩写为α→β|γ,以方便书写。
解释:
(VT∪VN) *:也就是VT∪VN的Kleene闭包
α≠ε:α不等于空符号串
用小写字母代表终结符,如:abc……,不能被拆分
用大写字母代表非终结符,如:ASBX……,可以被拆分
续:http://blog.csdn.net/wulingmin21/article/details/7485645