1.3.2.1. 示例¶

• \(\Sigma = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}\)

  \(L = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, ... \}\)

• \(\Sigma = \{a, b, c\}\)

  \(L = \{ab, ac, cabb\}\)

  有多少字符串可以属于 \(L\) ？ \(L\) 是一个包含 3 个字符串的语言，其中每个字符串都是由字母表中的符号构成的序列。

• \(\Sigma = \{a, b\}\)

  \(L = \{a^n b^n | n > 0\}\)

  这是一个无穷语言的例子。

  该语言中有哪些字符串？ \(\{ab, aabb, aaabbb, aaaabbbb, . . .\}\)

1.3.2.2. 记法¶

有用的记法：我们通常在本课程中使用这些符号。

• 对于某个字母表 \(\Sigma\) 中的符号，我们通常使用数字，或靠近常用英文字母表开头的字母：\(a, b, c, d, 0, 1\) 。

• 对于字符串名（也就是用来指代字符串的变量名），我们通常使用靠近常用英文字母表末尾的字母：\(u, v, w, x, y, z\) 。

1.3.2.3. 连接的定义¶

两个字符串 \(u\) 和 \(v\) 的连接，就是先包含 \(u\) 的所有符号、随后跟着 \(v\) 的所有符号的字符串。

示例：

设 \(w = a_1a_2...a_n\) 和 \(v=b_1b_2...b_n\)

那么， \(w \circ v\) 即 \(wv=a_1a_2...a_nb_1b_2...b_m\) 。

1.3.2.4. 字符串运算¶

字符串：\(w=abbc\) 、 \(v=ab\) 、 \(u=c\)

• 字符串的长度

  \(|w| + |v| = 6\)

• 连接

  \(v^3 = vvv = v \circ v \circ v = ababab\)

• \(v^0 = \lambda\) （空字符串）

• 字符串的逆序

  \(w^R = cbba\)

• \(|vv^Rw|= 8\)

• \(ab \circ λ = λ \circ ab = ab\)

• 一个由从 \(\Sigma\) 中串联在一起的0或更多个符号组成的字符串集合 \(\Sigma^∗ =\)

  示例：

  • \(\Sigma = \{a, b\}\)

  • \(\Sigma^* = \{\lambda, a, b, aa, ab, ba, bb, ...\}\)

    注意：最容易的做法是先列出所有长度为 0 的字符串，再列出长度为 1 的，然后长度为 2 的，依此类推。

  • \(\Sigma^+ = \Sigma^* - \{\lambda\}\)

  更多示例：

  \(\Sigma = \{a, b, c\}, L_1=\{ab, bc, aba\}, L_2 = \{c, bc, bcc\}\)

  • \(L_1 \cup L_2 = \{ab, bc, aba, c, bcc\}\)

  • \(L_1 \cap L_2 = \{bc\}\)

  • \(\overline{L_1} = \Sigma{}^{*} - L\)

  • \(\overline{L_1 \cap L_2} = \Sigma{}^{*} - \{bc\}\)

  • \(L_1 \circ L_2 = \{xy \mid x \in L_1\) 且 \(y\in L_2\} = \{abc, abbc, abbcc, bcc, bcbc, bcbcc, abac, ababc, ababcc\}\)

1.3.2.5. 定义¶

\(L^0 = \{\lambda\}\)

\(L^2 = L \circ L\)

\(L^3 = L \circ L \circ L\)

\(L^{*} = L^0 \cup L^1 \cup L^2 \cup L^3 \ldots\)

\(L^{+} = L^1 \cup L^2 \cup L^3 \ldots\)

1.3.3.1. 示例¶

推导一个句子：要推导一个句子，就从文法的起始点出发，不断进行替换，直到不能再替换为止。文法中的一个变量可以被其规则的右部替换

Fritz hit the ball

 <sentence> -> <subject><verb><d.o>
            -> <noun><verb><d.o> -> Fritz <verb><d.o.> -> Fritz hit <d.o.> -> Fritz hit <article><noun> -> Fritz hit the <noun> -> Fritz hit the ball

我们能推导出这些句子吗？如果不能，我们能否修改文法？

The ball hit Fritz

 球吃掉了球

• 如果一句句子遵循规则（文法能推导出它），那么它在语法上是正确的。

• 如果一句句子具有"意义"，那么它在语义上是正确的。

1.3.3.2. 文法的形式定义¶

一个文法 \(G = (V, T, S, P)\) ，其中

• \(V\) 是变量（非终结符）的一个有限集合。

• \(T\) 是终结符的一个有限集合（通常，它们是字符串）。

• \(S\) 是起始变量（ \(S \in V\) ）。

• \(P\) 是产生式（规则）的一个集合。

  \(x \rightarrow y\) 表示用 \(y\) 替换 \(x\) 。

这里， \(x \in (V \cup T)^+, y \in (V \cup T)^*\) 。

问题：在上面的"英语"文法示例中，\(S, T, V, P\) 分别是什么？

1.3.3.3. 记法¶

给定文法 \(G = (V, T, S, P)\) ，定义

现在，试着用语言来描述：这个文法的语言是什么？答案：它是基于字母表（即终结符集合，注意 \(T^*\) 是 T 上所有可能的字符串）构成的所有字符串的集合，且满足：如果你从 S（文法中的起始符号）出发，就能推导出这个字符串。

例题

\(G=(\{S\}, \{a,b\}, S, P)\)

\(P=\{S \rightarrow aaS, S \rightarrow b\}\)

\(L(G) =\) ?

答案：\(\{b, aab, aaaab, ... \} = \{(aa)^nb | n \ge 0\}\)

例题

\(L(G) = \{a^nccb^n | n > 0\}\)

\(G =\) ?

答案：

\(S \rightarrow aSb | aAb\)

\(A \rightarrow cc\)

例题

\(G = (\{S\}, \{a,b\}, S, P)\)

\(P = \{S \rightarrow aSb, S \rightarrow SS, S \rightarrow ab\}\)

这些字符串 \(aabb, abab, abba, babab\) 中，哪些可以由该文法生成？请给出推导过程。

\(L(G) =\) ?

答案：

这是匹配括号的语言，其中 \(a\) 是左括号， \(b\) 是右括号。

\(S \rightarrow aSb \rightarrow aabb\)

\(S \rightarrow SS \rightarrow abS \rightarrow abab\)

无法推导出 \(abba, babab\) 。为什么？没有哪个字符串以 \(a\) 结尾，也没有哪个字符串以 \(b\) 开头。