本文学习语言的定义。


还是继续前面的那个例子,下面是一个简化版本的英文文法。

<句子> -> <名词短语><动词短语>
<名词短语> -> <形容词><名词短语>
<名词短语> -> <名词>
<动词短语> -> <动词><名词短语>
<形容词> -> little
<名词> -> boy
<名词> -> apple
<动词> -> eat

假设现在有一个单词串little boy its apple,那么如何判定该词串是否满足给定的文法呢?

推导 (Derivations)和归约(Reductions)

为了回答这个问题,我们先来介绍两个概念:推导和归约。

给定文法G=((VT, VN,P,S),如果存在一个产生式α定义为β,那么可以将符号串γαδ中的α替换为β,也就是说,将γαδ重写(rewrite)为γβδ,记作 γαδ => γβδ。此时,称文法中的符号串 γαδ 直接推导(directly derive)出 γβδ。

简而言之,就是用产生式的右部替换产生式的左部。

如果α0=>α1,α1=>α2,α2=>α3,…,αn-1=>αn,则可以记作α0=>α1=>α2=>α3=> …=> αn-1=>αn,称符号串α0经过n步推导出αn,可简记为α1 => αn

当n等于1的时候,经过一步推导就是直接推导。当n等于0的时候,经过0步推导就是没有进行推导。

因此α经过零步推导得到的还是α,直接推导的正闭包表示经过正数步推导,也就是至少一步推导,直接推导的克林闭包表示”经过若干部推导”,这里可以是0步推导。

α=>0 α
=>+表示”经过正数步推导”
=>*表示”经过若干(可以是0)步推导”

下面我们来看一个推导的例子,这是一个简化版本的英文文法。

<句子> => <名词短语><动词短语>
=> <形容词><名词短语><动词短语>
=> little <名词短语><动词短语>
=> little <名词><动词短语>
=> little boy <动词短语>
=> little boy <动词><名词短语>
=> little boy eats <名词短语>
=> little boy eats <名词>
=> little boy eats apple

对于文法的开始符号<句子>,根据第一条产生式我们可以将产生式的左部句子替换为右部<名词短语>加上一个<动词短语>

接下来可以将<名词短语>根据第二条产生式把它替换成一个<形容词>加上一个<名词短语>

接下来可以将<形容词>根据第五条产生式替换成单词little。

按照这种方式,我们可以将<名词短语>替换成<名词>,然后将<名词>替换成boy,然后将<动词短语>替换成一个<动词>加上一个<名词短语>,然后将<动词>替换成eats。

这里我们需要注意的是,我们忽略英文单词的形态变化。也就是说将eat和异词看作是同一个词。

接下来可以将<名词短语>替换成<名词>,再将<名词>替换成apple。

这个自顶向下的过程就是一个推导的过程,也就是说,从文法的开始符号最后推出了一个词串。

与之相反的自底向上的过程,称之为是归约,推导的每一步是用产生式的右部来替换产生式的左部,而在归约的每一步是用产生式的左部来替换产生式的右部。

比如说将apple根据第七个产生式,将它替换成左部<名词>,<名词>我们又根据第三条产生式把它替换成左补<名词短语>

按照这种方式,我们可以这样eats替换成<动词>,将<动词>加上一个<名词短语>替换成<动词短语>

将boy替换成<名词>,将<名词>替换成<名词短语>,然后将little替换成<形容词>

<形容词>加上一个<名词短语>替换成<名词短语>最后<名词短语><动词短语>替换成文法的开始符号<句子>

由此可见归约是推导的逆过程,有了推导和归约的概念就可以回答前面的问题:也就是说有了文法(语言规则),如何判断一个词串是否是满足该文法的句子?

可以通过两种途径:

从文法的开始符号可以推导出这个词串,那么这个词串就是该语言的一个句子,这是从生成的角度来讲。

从这个词串可以归约出文法的开始符号,那么这个词串就是该语言一个句子,这是从识别的角度来讲。

无论是通过哪种途径,都需要根据规则来进行。

句型和句子

下面我们再来学习两个概念,句型和句子。

如果从文法的开始符号S经过若干步可以推导出一个文法符号串α,那么α就称为是这个文法的一个句型。由于α是一个文法符号串,因此一个句型中既可以包含终结符,也可以包含非终结符,也可能是空串。

如果 S => α,α∈(VT∪VN),则称α是G的一个句型 (sentential form)。

如果α中的每一个符号都是终结符,也就是说如果从文法的开始符号经过若干步可以推导出一个终结符号串w,那么这个终结符号串w就是该文法的一个句子,可见句子是一个特殊的句型,它是指不包含非终结符的句型。

如果 S => w,w ∈VT,则称w是G的一个句子(sentence)

例如在刚才的这个推导过程中,推导的每一步得到的符号串都是一个句型,而只有最后一个句型可以称之为是句子,因为在这个句型中没有非终结符。

<句子> => <名词短语><动词短语>
=> <形容词><名词短语><动词短语>
=> little <名词短语><动词短语>
=> little <名词><动词短语>
=> little boy <动词短语>
=> little boy <动词><名词短语>
=> little boy eats <名词短语>
=> little boy eats <名词>
=> little boy eats apple

语言的形式化定义

下面给出语言的形式化定义。由文法G的开始符号S推导出的所有句子构成的集合称为是文法G生成的语言记为L(G),这里L表示Language-语言。

由文法G的开始符号S推导出的所有句子构成的集合称为文法G生成的语言,记为L(G)。 即 L(G)= { w | S => w,w∈ VT }

大家可以想一下,这个算术表达式文法生成的语言中包含多少个句子? 我们都知道可以包含无穷多个句子,也就是说文法解决了无穷语言的有穷表示问题。

来看一个例子,下面是一个文法,那么这个文法生成的语言是什么呢?

S → L | LT
T → L | D | TL | TD
L → a | b | c | … | z
D → 0 | 1 | 2 | 3 |…| 9

先来看第四条产生式D定义为0或1或2一直到9,可见D表示的是数字digit;从第三条产生式L定义为a或b或c一直到z,可见L表示的是字母letter,那么T表示的是什么呢?

T定义为L或者D,可见T可以用来表示一个字母或者一个数字,根据T的后两个候选式T定义为TL或TD,也就是说我们可以将T替换成TL或TD。不妨假设将T替换成了TL,那么对于串上的这个非终结符T,根据第二条产生式可以继续将它替换成TL或者TD。不妨假设这一步将它替换成了TD。接下来可以对串上的T继续进行替换。假设这一步又把它替换成了TD,这个替换的过程可以一直进行下去。假如说最后一步,将串上的T替换成了D,那么我们最后得到的实际上是一个字母数字串。

T => TL
=> TDL
=> TDDL
=> TLDDL

=> TD…LDDL
=> DD…LDDL

最后我们再来看文法的开始符号S能推出什么。

S定义为L或者LT,也就是说S可以表示一个字母或者是一个字母后面加上一个字母数字串,概括起来也就是说S可以推出一个字母打头的字母数字串。这正是标识符的构成方法,所以说这个文法生成的语言实际上就是标识符。

语言上的运算

根据语言的定义,我们知道语言是一个集合,那么我们就可以在语言上进行一些集合运算。比如说并运算、连接运算、幂运算和闭包运算,需要注意的是语言L的0次幂就是由空串构成的集合。

来看一个例子,L是字母的集合,我们把它看作是一种语言,D是数字的结合,我们也把它看作是一种语言,那么LD上得到的就是由字母和数字构成的语言。

令L={A,B,…,Z,a,b,…,z},D={0,1, …,9}。则L(L∪D)*表示的语言是标识符

这个集合的闭包表示的是由字母数字串构成的集合,那么在L后面连接上(L∪D)闭包表示的就是由字母开头的字母数字串构成的集合,实际上也就是标识符的构成方法,因此这个语言表示的也是标识符。

最后修改日期:2020年5月14日

留言

撰写回覆或留言