Automata Theory 简明教程

Introduction to Grammars

在术语的文学意义上，语法指示自然语言会话的语法规则。自英语、梵语、汉语等自然语言诞生以来，语言学就尝试定义语法。

形式语言理论在大幅度上发现计算机科学领域中的适用性。 Noam Chomsky 在 1956 年给出了语法的数学模型，该模型可有效书写计算机语言。

Grammar

语法 G 可以形式化为一个 4 元组 (N、T、S、P)，其中 −

  1. N 或 VN 是变量或非终结符号的集合。

  2. T 或 ∑ 是终结符号的集合。

  3. S 是一个称为开始符号的特殊变量，S ∈ N

  4. P 是针对终结符号和非终结符号的生成规则。生成规则的格式为 α → β，其中的 α 和 β 是 VN ∪ ∑ 上的字符串，且 α 的至少一个符号属于 VN。

Example

语法 G1 −

({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})

在此，

  1. S, A, 和 B 是非终结符号；

  2. a 和 b 是终结符号

  3. S 是开始符号，S ∈ N

  4. 生成， P : S → AB, A → a, B → b

Example

语法 G2 −

(({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } )

在此，

  1. S 和 A 是非终结符号。

  2. a 和 b 是终结符号。

  3. ε 是空字符串。

  4. S 是开始符号，S ∈ N

  5. 产生式 P : S → aAb, aA → aaAb, A → ε

Derivations from a Grammar

字符串可以用语法中的产生式从其他字符串中派生。如果语法 G 有产生式 α → β ，我们可以说 x α y 在 G 中派生出 x β y 。此派生表示为 −

x α y ⇒G x β y

Example

让我们考虑语法 −

G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε } )

可以派生的字符串包括 −

S ⇒ aAb 使用产生式 S → aAb

⇒ aaAbb 使用产生式 aA → aAb

⇒ aaaAbbb 使用产生式 aA → aaAb

⇒ aaabbb 使用产生式 A → ε