Automata Theory 简明教程

Introduction to Grammars

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

n the literary sense of the term, grammars denote syntactical rules for conversation in natural languages. Linguistics have attempted to define grammars since the inception of natural languages like English, Sanskrit, Mandarin, etc.

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

The theory of formal languages finds its applicability extensively in the fields of Computer Science. Noam Chomsky gave a mathematical model of grammar in 1956 which is effective for writing computer languages.

Grammar

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

A grammar G can be formally written as a 4-tuple (N, T, S, P) where −

  1. N or VN is a set of variables or non-terminal symbols.

  2. T or ∑ is a set of Terminal symbols.

  3. S is a special variable called the Start symbol, S ∈ N

  4. P is Production rules for Terminals and Non-terminals. A production rule has the form α → β, where α and β are strings on VN ∪ ∑ and least one symbol of α belongs to VN.

Example

语法 G1 −

Grammar G1 −

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

在此，

Here,

  1. S, A, and B are Non-terminal symbols;

  2. a and b are Terminal symbols

  3. S is the Start symbol, S ∈ N

  4. Productions, P : S → AB, A → a, B → b

Example

语法 G2 −

Grammar G2 −

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

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

在此，

Here,

  1. S and A are Non-terminal symbols.

  2. a and b are Terminal symbols.

  3. ε is an empty string.

  4. S is the Start symbol, S ∈ N

  5. Production P : S → aAb, aA → aaAb, A → ε

Derivations from a Grammar

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

Strings may be derived from other strings using the productions in a grammar. If a grammar G has a production α → β, we can say that x α y derives x β y in G. This derivation is written as −

x α y ⇒G x β y

x α y ⇒G x β y

Example

让我们考虑语法 −

Let us consider the grammar −

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

可以派生的字符串包括 −

Some of the strings that can be derived are −

S ⇒ aAb 使用产生式 S → aAb

S ⇒ aAb using production S → aAb

⇒ aaAbb 使用产生式 aA → aAb

⇒ aaAbb using production aA → aAb

⇒ aaaAbbb 使用产生式 aA → aaAb

⇒ aaaAbbb using production aA → aaAb

⇒ aaabbb 使用产生式 A → ε

⇒ aaabbb using production A → ε