143 基本概念优秀课件.pptVIP

1.4.3 基本概念 对语言研究的三个方面 表示(representation)—— 无穷语言的表示。 有穷描述(finite description) ——研究的语言要么是有穷的，要么是可数无穷的，这里主要研究可数无穷语言的有穷描述。 结构(structure)——语言的结构特征。 1.4.3 基本概念 字母表(alphabet) 字母表是一个非空有穷集合，字母表中的元素称为该字母表的一个字母(letter)。又叫做符号(symbol)、或者字符(character)。 非空性。 有穷性。 例如： {a，b，c，d} { a，b，c，…，z} {0，1} 1.4.3 基本概念 字符的两个特性 整体性(monolith)，也叫不可分性。 可辨认性(distinguishable)，也叫可区分性。 例（续） {a，a′，b，b′} {aa，ab，bb} {∞，∧，∨，≥，≤} 1.4.3 基本概念 字母表的乘积(product) ∑1∑2={ab|a∈∑1，b∈∑2} 例如： {0,1}{0,1}={00，01，10，11} {0,1}{a，b，c，d}={0a，0b，0c，0d，1a，1b，1c，1d} {a，b，c，d}{0,1}={a0，a1，b0，b1，c0，c1，d0，d1} {aa，ab，bb}{0,1}={ aa0，aa1，ab0，ab1，bb0，bb1} 1.4.3 基本概念 字母表∑的n次幂 ∑0={ε} ∑n=∑n-1∑ ε是一个空句子。 思考：‘’和‘ ’是相等的吗？ 1.4.3 基本概念 ∑的正闭包 ∑+=∑∪∑2∪∑3∪∑4∪… ∑的克林闭包 ∑*=∑0∪∑+ =∑0∪∑∪∑2∪∑3∪… 1.4.3 基本概念 例如： {0,1}+={0，1，00，01，10，11，000，001，010，011，100，…} {0,1}*={ε，0，1，00，01，10，11，000，001，010，011，100，…} {a，b，c，d}+={a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，abc，…} {a，b，c，d}*={ε，a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，…，aaa，aab，aac，aad，aba，abb，abc,…} 1.4.3 基本概念 结论： ∑+={x|x是∑中的至少一个字符连接而成的字符串}。 ∑*={x|x是∑中的若干个，包括0个字符，连接而成的一个字符串}。 1.4.3 基本概念 句子(sentence) ∑是一个字母表，?x∈∑*，x叫做∑上的一个句子。 句子相等 两个句子被称为相等的，如果它们对应位置上的字符都对应相等。 句子的别称 字(word)、(字符、符号)行(line)、(字符、符号)串(string) 1.4.3 基本概念 出现(apperance) x，y∈∑*，a∈∑，句子xay中的a叫做a在该句子中的一个出现。 当x=ε时，a的这个出现为字符串xay的首字符 如果a的这个出现是字符串xay的第n个字符，则y的首字符的这个出现是字符串xay的第n+1个字符。 当y=ε时，a的这个出现是字符串xay的尾字符 例：abaabb。 1.4.3 基本概念 句子的长度(length) ?x∈∑*，句子x中字符出现的总个数叫做该句子的长度，记作|x|。 长度为0的字符串叫空句子，记作ε。 例如： |abaabb|=6 |bbaa|=4 |ε|=0 |bbabaabbbaa|=11 1.4.3 基本概念 并置(concatenation) x，y∈∑*，x，y的并置是由串x直接相接 串y所组成的。记作xy。并置又叫做连结。 串x的n次幂 x0=ε xn=xn-1x 1.4.3 基本概念 例如： 对x=001，y=1101 x0=y0=ε x4=001001001001 y4=1101110111011101 对x=0101，y=110110 x2 y2=110110110110 x4=0101010101010101 y4=110110110110110110110110 1.4.3 基本概念 ∑*上的并置运算性质 ⑴ 结合律：(xy)z=x(yz)。 ⑵ 左消去律：如果xy=xz，则y=z。 ⑶ 右消去律：如