什么是 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 是语法上正确的英语句子}

更新于: 2021 年 6 月 11 日

9K+ 浏览量

启动您的 职业生涯

通过完成课程获得认证

开始学习
广告