--- title: 通识学习:形式语言与自动机,布尔代数与数进制 abbrlink: 10621 date: "2025-03-07 15:52:11" updated: "2025-07-04 18:44:32" desc: "好多东西都是似曾相识的.要么是在上学期就讲过,要么是中学时期就有过了解.这学期开学一周,所学到的基础知识有这几点:" categories: - 学校学习 tags: - 学习 - 记录 --- ## 这一周的学习环环相扣 ### 概览 好多东西都是似曾相识的.要么是在上学期就讲过,要么是中学时期就有过了解.这学期开学一周,所学到的基础知识有这几点: | 课程 | 内容 | | -------------------- | ------------------------------------------------------------------------------------- | | **形式语言与自动机** | **计算理论**学的,在**编译原理**的课上,老师又给大家讲了一遍 | | 布尔代数 | **真($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} $$ --- **作者：**xingwangzhe **本文链接：**[https://xingwangzhe.fun/posts/10621/](https://xingwangzhe.fun/posts/10621/) 本文采用[知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议](https://creativecommons.org/licenses/by-nc-sa/4.0/)进行许可。