文法和语言

code-child

发布于 2023-05-30 11:16:12

4620

文章被收录于专栏：codechildcodechild

=字母表

字母表是一个有穷符号集合符号：字母、数字、标点符号、……

字母表上的运算

假设字母表用∑\sum∑表示

字母表的乘积——就是求笛卡儿积

例如：{0,1}{a,b}={0a,0b,1a,1b}

字母表的n次幂

∑0\sum0∑0={ε} (∑)n(\sum)^n(∑)n={(∑)n−1∑(\sum) ^{n-1}\sum(∑)n−1∑} 例如：{0，1}的3次方={0，1}{0，1}{0，1}={000，001，010，011，100，101，110，111} 字母表中的n次幂：长度为n的符号串构成的集合

字母表的正闭包——U表示的并集

(∑)+=∑U(∑)2U(∑)3....(\sum)^+=\sum U (\sum)^2 U(\sum)^3....(∑)+=∑U(∑)2U(∑)3.... 字母表的正闭包：长度正数的符号串构成的集合

字母表的克林闭包

(∑)∗=(∑)0U(∑)U(∑)2U(∑)3....(\sum)^*=(\sum)^0 U(\sum) U (\sum)^2 U(\sum)^ 3....(∑)∗=(∑)0U(∑)U(∑)2U(∑)3.... 克林闭包就是在正闭包的基础上在添加一个空串。字母表的克林闭包：任意符号串（长度可以为0）构成的集合。

串

设∑\sum∑是一个字母表，对于任意的x属于(∑)∗(\sum)^*(∑)∗,x称为是∑\sum∑上的一个串。

串是字母表中符号的一个有穷序列。

串s的长度，通常记作|s|，是指s中符号的个数。
空串是长度为0的串，用ε表示，|ε|=0。

串上的运算——连接

如果x和y是串，你们x和y的连接是把y附加到x后面而形成的串，记作xy。
空串是连接运算的单位元，即，对于任意串s都有，εs=sε=s

设x,y,z是三个字符串，如果x=yz;则称y是x的前缀，z是x的后缀

串上的运算——幂

串s的幂运算

s0=εs^0=εs0=ε sn=sn−1ss^n=s^{n-1}ssn=sn−1s

例如：如果s=ba,那么s1=ba,s2=baba,s3=bababas^1=ba,s^2=baba,s^3=bababas1=ba,s2=baba,s3=bababa…… 串s的n次幂：将n个s连接起来。

文法的定义

文法的形式定义

四元组：G=(VT,VN,P,S)G=(V_T,V_N,P,S)G=(VT,VN,P,S)

VTV_TVT：终结符集合

终结符是文法所定义的语言的基本符号。例如：在英语的句子中，终结符就是一个一个的单词。

VNV_NVN:非终结符集合

非终结符是用来表示语法成分的符号，有时也称为“语法变量” 注意： 终结符集合与非终结符符集合的交集为空集。终结符集合与非终结符符集合的并集为文法符号集

P：产生式集合

产生式描述了将终结符和非终结符组合成串的方法。产生式的一般形式：α->β；读作：α定义为β α∈(VTUVN)+α∈(V_TUV_N)^+α∈(VTUVN)+，且α中至少包含VnV_nVn中的一个元素，称为产生式的左部 β∈(VTUVN)∗β∈(V_TUV_N)^*β∈(VTUVN)∗：称为产生式的体或右部