解释 TOC 中正则语言的不同操作。

  • Z时代
  • 2024-01-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 保留字}

    = {开始，结束，如果，...}

  • E = {Pascal 保留字} U { (, ), ., :, ;,...} U {Legal Pascal identifiers}

    L = {x | x 在 E* 中，x 是语法正确的 Pascal 程序}

  • E = {英文单词}

    L = {x | x 在 E* 中，x 是语法正确的英语句子}

对正则语言的操作

对常规语言的一些操作如下 -

  • 联盟

  • 路口

  • 区别

  • 级联

  • 克莱恩 * 关闭

让我们一一了解这些操作。

联盟

如果 Ll 和 If L2 是两种正则语言，它们的并集 Ll u L2 也将是正则的。

例如，Ll = {an I n > O} 和 L2 = {bn I n > O}

L3 = Ll U L2 = {an U bn I n > O} 也是正则的。

路口

如果 Ll 和 If L2 是两种正则语言，它们的交集 Ll n L2 也将是正则的。

例如，

Ll= {am bn I n > 0 and m > O} 和

L2= {am bn U bn am I n > 0 and m > O}

L3 = Ll n L2 = {am bn I n > 0 and m > O} 也是规则的。

级联

如果 L1 和 If L2 是两种常规语言，则它们的串联 L1.L2 也将是常规的。

例如，

Ll = {an I n > 0} 和 L2 = {bn I n > O}

L3 = L1.L2 = {am . bn I m > 0 和 n > O} 也是规则的。

Kleene 闭包

如果 Ll 是正则语言，则其 Kleene 闭包 Ll* 也将是正则的。

例如，Ll = (a U b ), Ll* = (a U b)*

补充

如果L(G)是正则语言，它的补L'(G)也将是正则的。可以通过L(G)从所有可能的字符串中减去包含的字符串来找到语言的补码。

例如，

L(G) = {an I n > 3}

L'(G) = {an I n <= 3}

注意：如果两个正则表达式生成的语言相同，则它们是等价的。例如，(a+b*)* 和 (a+b)* 生成相同的语言。每个由 (a+b*)* 生成的字符串也由 (a+b)* 生成，反之亦然。

示例 1

在集合 l 上写出接受 a 的所有组合的语言的正则表达式：= {a}

a 的所有组合均值 a 可以是零、单、双等。如果 a 出现零次，则表示空字符串。也就是说，我们期望集合 {E, a, aa, aaa, ....}。

所以我们为此给出一个正则表达式如下 -

R = a*

那是克林闭包了。

以上是 解释 TOC 中正则语言的不同操作。 的全部内容， 来源链接： utcz.com/z/331768.html

回到顶部