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

这一周的学习环环相扣

概览

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

课程	内容
形式语言与自动机	计算理论学的,在编译原理的课上,老师又给大家讲了一遍
布尔代数	真($1$)与假($0$).与或非这些个概念早年在高中时期学集合论的时候有过了解
进制转换	2,8,10,16等等,都是比较常用的进制了

形式语言与自动机

基本概念

字母表（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$

语法生成树：

    S
   / \
  A   B
 /|   |\
a A b c B d
  |     |
  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）或 ^（编程语言中常用）
• 逻辑定义：
  当且仅当两个输入不同时，结果为真。
• 真值表：

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

2. 同或（XNOR）

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

A	B	A⊙B
0	0	1
0	1	0
1	0	0
1	1	1

3. 与非（NAND）

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

A	B	A↑B
0	0	1
0	1	1
1	0	1
1	1	0

4. 或非（NOR）

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

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

• 真值表：

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

进制转换详解

以下是常见进制的表达:

进制	英文	范围	前缀	后缀
二进制	Binary	0-1	0B	B
八进制	Octal	0-7	0O	O
十进制	Decimal	0-9	无	D
十六进制	Hexadecimal	0-9,A-F	0x	H

例如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}$$