语言的定义

àì夳堔傛蜴生んèń 2022-03-26 10:11 137阅读 0赞

### 文章目录 ###

*  推导(Derivations)和规约(Reductions)
 *  句型和句子
 *  语言的形式化定义

# 推导(Derivations)和规约(Reductions) #

给定文法 G = \{ V T , V N , P , S \} G=\\\{V\_T,V\_N,P,S\\\} G=\{ VT,VN,P,S\}，如果 α → β ∈ P \\alpha \\rightarrow\{\\beta\} \\in P α→β∈P，那么可以将符号串 γ α δ \\gamma \\alpha \\delta γαδ中的 α \\alpha α**替换**成 β \\beta β，也就是说，将 γ α δ \\gamma \\alpha \\delta γαδ**重写** 为 γ β δ \\gamma \\beta \\delta γβδ，记作 γ α δ ⇒ γ β δ \\gamma \\alpha \\delta \\Rightarrow \{\\gamma \\beta \\delta\} γαδ⇒γβδ。此时，称文法中的符号串 γ α δ \\gamma \\alpha \\delta γαδ直接推导出 γ β δ \\gamma \\beta \\delta γβδ。

简而言之，**推导**就是**用产生式的右部替换产生式的左部**。

如果 a 0 ⇒ a 1 , a 1 ⇒ a 2 , . . . , a n − 1 ⇒ a n a\_0 \\Rightarrow\{a\_1\}, a\_1 \\Rightarrow\{a\_2\},...,a\_\{n-1\} \\Rightarrow\{a\_n\} a0⇒a1,a1⇒a2,...,an−1⇒an，则可以记作 a 0 ⇒ a 1 ⇒ a 2 ⇒ . . . ⇒ a n − 1 ⇒ a n a\_0 \\Rightarrow\{a\_1 \\Rightarrow\{a\_2 \\Rightarrow\{... \\Rightarrow\{a\_\{n-1\} \\Rightarrow\{a\_n\}\}\}\}\} a0⇒a1⇒a2⇒...⇒an−1⇒an，称符号串**经过n步推导出** a n a\_n an，可简记为 a 0 ⇒ n a n a\_0 \\Rightarrow\{^na\_n\} a0⇒nan

*   a ⇒ 0 a a \\Rightarrow\{^0a\} a⇒0a
 *   ⇒ + \\Rightarrow ^+ ⇒\+表示经过正数步推导
 *   ⇒ ∗ \\Rightarrow ^\* ⇒∗经过若干（可以是0）步推导

**而规约就是用产生式的左部替换产生式的右部**。

如何判断某一词串是否是该语言的句子？

*  句子的推导
 *  句子的规约

# 句型和句子 #

如果 S ⇒ ∗ a , a ∈ ( V T ∪ V N ) ∗ S \\Rightarrow^\*\{a\},a \\in (V\_T \\cup V\_N)^\* S⇒∗a,a∈(VT∪VN)∗，则称 α \\alpha α是`G`的一个句型（sentence form）。

由于 α \\alpha α是一个文法符号串，所以一个句型中既可以包含终结符，又可以包含非终结符，也可能是空串。

如果 S ⇒ ∗ w , w ∈ V T ∗ S \\Rightarrow^\*\{w\}, w \\in V\_T^\* S⇒∗w,w∈VT∗，则称 w w w是`G`的一个句子，句子是不包含非终结符的句型。

# 语言的形式化定义 #

由文法`G`的开始符号`S`推导出的所有**句子**构成的集合称为文法G生成的语言，记为`L(G)`。即

L ( G ) = \{ w ∣ S ⇒ ∗ w , w ∈ V T ∗ \} L(G) = \\\{w | S \\Rightarrow^\*w,w \\in V\_T^\* \\\} L(G)=\{ w∣S⇒∗w,w∈VT∗\}

例如：文法G

1.   S → L ∣ L T S \\rightarrow\{L | LT\} S→L∣LT
2.   T → L ∣ D ∣ T L ∣ T D T \\rightarrow\{L | D | TL | TD\} T→L∣D∣TL∣TD
3.   L → a ∣ b ∣ c ∣ . . . ∣ z L \\rightarrow\{a|b|c|...|z\} L→a∣b∣c∣...∣z
4.   D → 0 ∣ 1 ∣ 2 ∣ . . ∣ 9 D \\rightarrow\{0|1|2|..|9\} D→0∣1∣2∣..∣9

那么该文法表达的意思是一个字母或者是由字母开头，后接字母数字串的语言。