通识学习:形式语言与自动机,布尔代数与数进制

这一周的学习环环相扣

概览

好多东西都是似曾相识的.要么是在上学期就讲过,要么是中学时期就有过了解.这学期开学一周,所学到的基础知识有这几点:

形式语言与自动机

基本概念

字母表（Alphabet）

定义：一个有限的非空符号集合，通常用 $\Sigma$ 表示。 例：$\Sigma = \{a, b\}$，$\Sigma = \{0, 1\}$

字符串（String）

定义：从字母表中的符号构成的有限序列。 例：在 $\Sigma = \{a, b\}$ 上，$abba$, $bab$, $\varepsilon$（空串）都是字符串。

形式语言（Formal Language）

定义：在给定字母表上的字符串的集合。 例：$L = \{a^nb^n | n \geq 0\}$，表示所有由相同数量的a和b组成的字符串。

语法和语言分类

句型（Sentential Form）

定义：在推导过程中出现的、可能包含非终结符的字符串。

短语（Phrase）

定义：在推导过程中可以从某非终结符推导出的句型的一部分。

简单短语（Simple Phrase）

定义：在一步推导中由单个非终结符直接产生的子串。

句柄（Handle）

定义：在最右推导的逆过程中，句型中最左边的、能够被归约的产生式右部。

复杂示例：

考虑文法 $G = (V_N, V_T, P, S)$，其中：

• $V_N = \{S, A, B\}$：非终结符集合
• $V_T = \{a, b, c, d\}$：终结符集合
• $P$：产生式集合，包含以下规则：
  • $S \rightarrow AB$
  • $A \rightarrow aAb | ab$
  • $B \rightarrow cBd | cd$
• $S$：开始符号

对于字符串 $w = aabccd$：

推导与语法生成树

1. 推导（Derivation）

定义：从起始符号出发，通过连续应用产生式规则得到字符串的过程。 例：左推导（最左非终结符优先）、右推导（最右非终结符优先）

2. 语法生成树（Syntax Tree）

定义：表示推导过程的层次结构，根节点是起始符号，叶节点从左到右构成推导的字符串。

示例： 对于文法 $G = (V_N, V_T, P, S)$，其中：

• $V_N = \{S, A, B\}$：非终结符集合
• $V_T = \{a, b, c, d\}$：终结符集合
• $P$：产生式集合，包含以下规则：
  • $S \rightarrow AB$
  • $A \rightarrow aAb | ab$
  • $B \rightarrow cBd | cd$
• $S$：开始符号

推导过程：$S \Rightarrow AB \Rightarrow aAbB \Rightarrow aabB \Rightarrow aabcBd \Rightarrow aabccd$

语法生成树：

1
     S
2
    / \
3
   A   B
4
  /|   |\
5
 a A b c B d
6
   |     |
7
   a b   c d

句型、短语、简单短语与句柄

句型（Sentential Form）

定义：在推导过程中出现的字符串，可能包含终结符和非终结符。 特点：是从起始符号开始，经过零步或多步推导得到的字符串。

短语（Phrase）

定义：如果存在推导 $S \Rightarrow^* \alpha A \beta \Rightarrow^* \alpha \gamma \beta$，那么 $\gamma$ 是相对于非终结符 $A$ 的一个短语。 特点：是句型中可以追溯到某个非终结符的子串。

简单短语（Simple Phrase）

定义：如果 $A \rightarrow \gamma$ 是一个产生式，且存在推导 $S \Rightarrow^* \alpha A \beta \Rightarrow \alpha \gamma \beta$，那么 $\gamma$ 是一个简单短语。 特点：是在一步推导中直接由一个非终结符产生的子串。

句柄（Handle）

定义：在最右推导的逆过程中，可以被归约的最左边的产生式右部。 特点：是规范归约过程中第一个被识别和归约的部分。

示例分析

对于上述文法和字符串 $w = aabccd$ 的推导：

1. 句型：$S$, $AB$, $aAbB$, $aabB$, $aabcBd$, $aabccd$ 都是句型。
2. 短语：在句型 $aabcBd$ 中，$aab$ 是从 $A$ 推导出的短语，$cBd$ 是从 $B$ 推导出的短语。
3. 简单短语：在 $aAbB$ 中应用 $A \rightarrow ab$ 产生 $aabB$ 时，$ab$ 是一个简单短语。
4. 句柄：在句型 $aabccd$ 的规范归约中，第一个句柄是 $cd$（对应产生式 $B \rightarrow cd$）。

布尔代数

值:真与假,这个很好理解

与或非,这三个就不说了,太简单了,写一些别的

1. 异或（XOR）

• 符号：⊕（LaTeX：\oplus）或 ^（编程语言中常用）
• 逻辑定义： 当且仅当两个输入不同时，结果为真。
• 真值表：

2. 同或（XNOR）

• 符号：⊙（LaTeX：\odot）或 ≡（LaTeX：\equiv）
• 逻辑定义： 当且仅当两个输入相同时，结果为真（异或的非）。
• 真值表：

3. 与非（NAND）

• 符号：↑（LaTeX：\uparrow）或 ¬(A ∧ B)
• 逻辑定义： 先进行与运算，再取反。
• 真值表：

4. 或非（NOR）

• 符号：↓（LaTeX：\downarrow）或 ¬(A ∨ B)

• 逻辑定义： 先进行或运算，再取反。

• 真值表：

  A	B	A↓B
  0	0	1
  0	1	0
  1	0	0
  1	1	0

进制转换详解

以下是常见进制的表达:

例如17O表达的是八进制下的数字,(也就是15D或者是15(因为十进制很常见,忽略后缀D的话默认是十进制))

$N$进制转换到十进制

将任意进制数转换为十进制的通用方法是：按权展开相加法

操作步骤

1. 确定进制：明确当前进制数的基数N（如二进制N=2，十六进制N=16）
2. 分解位权：从右到左为每一位数字标注位权（从0开始递增）
3. 按权相乘：每一位数字乘以N的位权次方
4. 求和：将所有乘积相加得到十进制结果

示例说明

二进制转十进制

二进制数：1011.1011B 计算过程：

$$1011.1011B = 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 1 \times 2^0 + 1 \times 2^{'{'}-1{'}'} + 0 \times 2^{'{'}-2{'}'} + 1 \times 2^{'{'}-3{'}'} + 1 \times 2^{'{'}-4{'}'} = 11.6875$$

通解

$T$代表进制符号

$T进制数:abcd.efghT$

$abcd.efghT= a\times T^3+b\times T^2 + c\times T + d\times T^0 +e\times T^{-1} + f\times T^{-2} +g\times T^{-3} + h\times T^{-4}$

更进一步地

对任意$T进制数a*na*{n-1}a*{n-2}...a_0.a*{-1}a*{-2}a*{-3}...a\_{-m}T |{m,n}\in N$

转到十进位制为 $S = \sum\limits\_{i=-m}^n a_i\times T^i$

十进制转$N$进制

操作步骤

1. 整数部分：除N取余法

• 用N除十进制数，记录余数
• 用商继续除以N，直到商为0
• 从下往上读取所有余数，得到N进制的整数部分

2. 小数部分：乘N取整法

• 小数部分乘以N，取整数部分作为N进制的一位
• 取小数部分继续乘以N，重复直到小数部分为0或达到所需精度

示例说明

十进制转二进制

整数部分：将25转为二进制

$$\begin{'{'}align{'}'} 25 &= 2 \times 12 + \textcolor{'{'}red{'}'}{'{'}1{'}'} \ 12 &= 2 \times 6 + \textcolor{'{'}red{'}'}{'{'}0{'}'} \ 6 &= 2 \times 3 + \textcolor{'{'}red{'}'}{'{'}0{'}'} \ 3 &= 2 \times 1 + \textcolor{'{'}red{'}'}{'{'}1{'}'} \ 1 &= 2 \times 0 + \textcolor{'{'}red{'}'}{'{'}1{'}'} \end{'{'}align{'}'}$$

从下往上读：11001B

小数部分：将0.625转为二进制

$$\begin{'{'}align{'}'} 0.625 \times 2 &= 1.25 \rightarrow \textcolor{'{'}red{'}'}{'{'}1{'}'} \ 0.25 \times 2 &= 0.5 \rightarrow \textcolor{'{'}red{'}'}{'{'}0{'}'} \ 0.5 \times 2 &= 1.0 \rightarrow \textcolor{'{'}red{'}'}{'{'}1{'}'} \end{'{'}align{'}'}$$

从上往下读：.101B

结果：$25.625_D = 11001.101_B$

二进制转八进制、十六进制

操作步骤

1. 将二进制数从小数点处分开，分别处理整数部分和小数部分
2. 八进制转换：每3位二进制对应1位八进制
3. 十六进制转换：每4位二进制对应1位十六进制
4. 如果位数不足，整数部分左侧补0，小数部分右侧补0

示例说明

二进制转八进制

$$\begin{'{'}array{'}'}{'{'}rcl{'}'} \text{'{'}二进制：{'}'} & 1011010.101_B \ \text{'{'}分组：{'}'} & 001|011|010.101|000 \ \text{'{'}八进制：{'}'} & 1\quad3\quad2.5\quad0 \ \text{'{'}结果：{'}'} & 132.50_O \end{'{'}array{'}'}$$

二进制转十六进制

$$\begin{'{'}array{'}'}{'{'}rcl{'}'} \text{'{'}二进制：{'}'} & 1011010.101_B \ \text{'{'}分组：{'}'} & 0101|1010.1010 \ \text{'{'}十六进制：{'}'} & 5\quad A.A \ \text{'{'}结果：{'}'} & 5A.A_H \end{'{'}array{'}'}$$

八进制、十六进制转二进制

操作步骤

1. 将八进制/十六进制数从小数点处分开
2. 八进制转换：每1位八进制对应3位二进制
3. 十六进制转换：每1位十六进制对应4位二进制

示例说明

八进制转二进制

$$\begin{'{'}array{'}'}{'{'}rcl{'}'} \text{'{'}八进制：{'}'} & 76.24_O \ \text{'{'}转换：{'}'} & 7 \rightarrow 111 \ & 6 \rightarrow 110 \ & . \rightarrow . \ & 2 \rightarrow 010 \ & 4 \rightarrow 100 \ \text{'{'}结果：{'}'} & 111110.010100_B \end{'{'}array{'}'}$$

十六进制转二进制

$$\begin{'{'}array{'}'}{'{'}rcl{'}'} \text{'{'}十六进制：{'}'} & 3A.C8_H \ \text{'{'}转换：{'}'} & 3 \rightarrow 0011 \ & A \rightarrow 1010 \ & . \rightarrow . \ & C \rightarrow 1100 \ & 8 \rightarrow 1000 \ \text{'{'}结果：{'}'} & 0011,1010.1100,1000_B \end{'{'}array{'}'}$$