什么是 TOC 的基本概念?
下面解释了理论计算机科学 (TOC) 中基本概念的基本定义以及相关示例:
符号
符号简单地称为字符。
它是一个原子单元,例如数字、字符、小写字母等。有时它也是一个单词。形式语言不涉及符号的“含义”。
例如:
- a,b,c,……………z
- 0,1,2,…………..9
- +,-,*,%,…………特殊字符。
字母表
字符集称为字母表。
字母表是有限的、非空的符号集。用 Σ 或 E 表示。
例如:
- Σ ={0,1} 二进制字母表集。
- Σ ={a,b,c,……..,z} 所有小写字母的集合。
- Σ ={A,B,C,………Z} 所有大写字母的集合。
- Σ ={+,&,%,……….} 所有特殊字符的集合。
字符串或单词
字符串是从某个字母表中选择的一系列有限符号。
例如:
- 00011001 是来自二进制字母表 Σ={0,1} 的字符串,而 aabbcabcd 是来自字母表 Σ={a,b,c,d} 的字符串。
- 如果,w = 0110 y = 0aa x = aabcaa z = 111,则:
- 特殊字符串 − s(也用 X 表示)
- 连接 − wz = 0110111
- 长度 − |w| = 4 |s| = 0 |x| = 6
- 反转 − yR = aa0
一些特殊的字符串集如下:
- E* E 中所有符号的字符串
- E+ E* - {s}
例如:
- E = {0, 1}
- E* = {s, 0, 1, 00, 01, 10, 11, 000, 001,...}
- E+ = {0, 1, 00, 01, 10, 11, 000, 001,.}
字符串长度
它是字符串或单词中符号的数量。用 |w| 表示。
例如:
w=01011001 来自二进制字母表 Σ={0,1}
|w| = 8
X= abbaddabba 来自二进制字母表 Σ={a,b}
|X| = 10
语言
语言是从某个字母表(有限或无限)中选择的一组字符串。换句话说,E* 的任何子集 L 都是 TOC 中的语言。
一些特殊的语言如下:
- {} 空集/语言,不包含任何字符串。
- {s} 包含一个字符串(空字符串)的语言。
示例
E = {0, 1}
L = {x | x 属于 E* 且 x 包含偶数个 0}
E = {0, 1, 2,., 9, .}
L = {x | x 属于 E* 且 x 构成一个有限长度的实数}
= {0, 1.5, 9.326,.}
E = {a, b, c,., z, A, B,., Z}
L = {x | x 属于 E* 且 x 是 Pascal 保留字}
= {BEGIN, END, IF,...}
E = {Pascal 保留字} U { (, ), ., :, ;,...} U {合法的 Pascal 标识符}
L = {x | x 属于 E* 且 x 是语法上正确的 Pascal 程序}
E = {英语单词}
L = {x | x 属于 E* 且 x 是语法上正确的英语句子}
广告