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

这一周的学习环环相扣

概览

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

形式语言与自动机

基本概念

字母表（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）或 ^（编程语言中常用）
• 逻辑定义： 当且仅当两个输入不同时，结果为真。
• 真值表：

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}