🕒 阅读时间：4 分钟 📝 字数：1545 👀 阅读量： Loading...
好多东西都是似曾相识的.要么是在上学期就讲过,要么是中学时期就有过了解.这学期开学一周,所学到的基础知识有这几点:
| 课程 | 内容 |
|---|---|
| 形式语言与自动机 | 计算理论学的,在编译原理的课上,老师又给大家讲了一遍 |
| 布尔代数 | 真(11)与假(00).与或非这些个概念早年在高中时期学集合论的时候有过了解 |
| 进制转换 | 2,8,10,16等等,都是比较常用的进制了 |
定义：一个有限的非空符号集合，通常用 Σ\Sigma 表示。 例：Σ={a,b}\Sigma = \{a, b\}，Σ={0,1}\Sigma = \{0, 1\}
定义：从字母表中的符号构成的有限序列。 例：在 Σ={a,b}\Sigma = \{a, b\} 上，abbaabba, babbab, ε\varepsilon（空串）都是字符串。
定义：在给定字母表上的字符串的集合。 例：L={anbn∣n≥0}L = \{a^nb^n | n \geq 0\}，表示所有由相同数量的a和b组成的字符串。
定义：在推导过程中出现的、可能包含非终结符的字符串。
定义：在推导过程中可以从某非终结符推导出的句型的一部分。
定义：在一步推导中由单个非终结符直接产生的子串。
定义：在最右推导的逆过程中，句型中最左边的、能够被归约的产生式右部。
复杂示例：
考虑文法 G=(VN,VT,P,S)G = (V_N, V_T, P, S)，其中：
对于字符串 w=aabccdw = aabccd：
定义：从起始符号出发，通过连续应用产生式规则得到字符串的过程。 例：左推导（最左非终结符优先）、右推导（最右非终结符优先）
定义：表示推导过程的层次结构，根节点是起始符号，叶节点从左到右构成推导的字符串。
示例： 对于文法 G=(VN,VT,P,S)G = (V_N, V_T, P, S)，其中：
推导过程：S⇒AB⇒aAbB⇒aabB⇒aabcBd⇒aabccdS \Rightarrow AB \Rightarrow aAbB \Rightarrow aabB \Rightarrow aabcBd \Rightarrow aabccd
语法生成树：
S
/ \
A B
/| |\
a A b c B d
| |
a b c d
定义：在推导过程中出现的字符串，可能包含终结符和非终结符。 特点：是从起始符号开始，经过零步或多步推导得到的字符串。
定义：如果存在推导 S⇒∗αAβ⇒∗αγβS \Rightarrow^* \alpha A \beta \Rightarrow^* \alpha \gamma \beta，那么 γ\gamma 是相对于非终结符 AA 的一个短语。 特点：是句型中可以追溯到某个非终结符的子串。
定义：如果 A→γA \rightarrow \gamma 是一个产生式，且存在推导 S⇒∗αAβ⇒αγβS \Rightarrow^* \alpha A \beta \Rightarrow \alpha \gamma \beta，那么 γ\gamma 是一个简单短语。 特点：是在一步推导中直接由一个非终结符产生的子串。
定义：在最右推导的逆过程中，可以被归约的最左边的产生式右部。 特点：是规范归约过程中第一个被识别和归约的部分。
对于上述文法和字符串 w=aabccdw = aabccd 的推导：
值:真与假,这个很好理解
与或非,这三个就不说了,太简单了,写一些别的
⊕（LaTeX：\oplus）或 ^（编程语言中常用）| A | B | A⊕B |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
⊙（LaTeX：\odot）或 ≡（LaTeX：\equiv）| A | B | A⊙B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
↑（LaTeX：\uparrow）或 ¬(A ∧ B)| A | B | A↑B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
符号：↓（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的话默认是十进制))
将任意进制数转换为十进制的通用方法是：按权展开相加法
二进制转十进制
二进制数：1011.1011B 计算过程：
1011.1011B=1×23+0×22+1×21+1×20+1×2−1+0×2−2+1×2−3+1×2−4=11.68751011.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
通解
TT代表进制符号
T进制数:abcd.efghTT进制数:abcd.efghT
abcd.efghT=a×T3+b×T2+c×T+d×T0+e×T−1+f×T−2+g×T−3+h×T−4abcd.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−1a∗n−2...a0.a∗−1a∗−2a∗−3...a_−mT∣m,n∈NT进制数a*na*{n-1}a*{n-2}...a_0.a*{-1}a*{-2}a*{-3}...a\_{-m}T |{m,n}\in N
转到十进位制为 S=∑_i=−mnai×TiS = \sum\limits\_{i=-m}^n a_i\times T^i
十进制转二进制
整数部分：将25转为二进制
25=2×12+112=2×6+06=2×3+03=2×1+11=2×0+1\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转为二进制
0.625×2=1.25→10.25×2=0.5→00.5×2=1.0→1\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.625D=11001.101B25.625_D = 11001.101_B
二进制转八进制
二进制：1011010.101B分组：001∣011∣010.101∣000八进制：132.50结果：132.50O\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}
二进制转十六进制
二进制：1011010.101B分组：0101∣1010.1010十六进制：5A.A结果：5A.AH\begin{array}{rcl} \text{二进制：} & 1011010.101_B \\ \text{分组：} & 0101|1010.1010 \\ \text{十六进制：} & 5\quad A.A \\ \text{结果：} & 5A.A_H \end{array}
八进制转二进制
八进制：76.24O转换：7→1116→110.→.2→0104→100结果：111110.010100B\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}
十六进制转二进制
十六进制：3A.C8H转换：3→0011A→1010.→.C→11008→1000结果：0011 1010.1100 1000B\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}
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。