10

例如，在给我的作业中，我们被要求找出两个正则表达式是否相等。

(a+b+c)*  and ((ab)**c*)*

我的问题是如何做到这一点？如果我为两者绘制转换图，然后通过它运行一些字符串并显示两个 TG 都能够接受它，这是一个充分的证据吗？如果没有，我该怎么做？对此有数学/公理化方法吗？

提前致谢。

编辑：我想澄清另一件事，这与这个问题有关。下图中描绘的两个 FA 是否相同？

在此处输入图像描述

即上图中的（1）和（2）是一样的吗？

4

6 回答 6

7

有一个算法可以确定它们是否相等：

  1. 使用 Kleene 定理构造对应于每个 RE 的 NFA-lambdas
  2. 使用子集/幂集构造为每个构造 DFA
  3. （可选）使用标准 DFA 最小化算法最小化 DFA。
  4. 使用笛卡尔积机器构造为 L(M1) \ L(M2) 和 L(M2) \ L(M1) 构造 DFA
  5. （可选）最小化这些 CPM。
  6. 通过测试大小不大于 |Q| 的字母 E 上的所有字符串来确定每个字符串是否接受任何字符串 （由于常规语言的抽引引理而起作用）

不需要新奇或天才；您可以编写一个程序来执行此操作（尽管在实践中，使用 powerset 构造可能很笨拙，并且未能在两个步骤中最小化可能代价高昂）。

编辑：是的，那些 DFA 是一样的。第一个只是第二个的简写符号。

于 2012-01-22T15:51:07.500 回答
4

如果由 R 定义的语言（即由正则表达式 R 生成的字符串集合）等于由 T 定义的语言，则两个正则表达式 R 和 T 是等价的。为了证明正则表达式的等价性，我们使用集合论的包含证明. 也就是说，如果 S1 是正则表达式 R 生成的字符串集合，S2 是正则表达式 T 生成的字符串集合，我们必须证明 S1 ⊆ S2 和 S2 ⊆ S1。这两个方向都是证明集合相等所必需的。

-- 摘自 CSc 4340 GSU Fall 09 的讲义（Dr. Raj Sunderraman）

于 2012-01-22T14:39:35.577 回答
3

假设

  1. 插入空格用于说明
  2. ( ( a b )* * c* )*实际上是((ab)*c*)**，
  3. 每个模式都由^和包裹$。

那些正则表达式不一样。

abccabcc不会匹配(a+b+c)*但会匹配((ab)*c*)*

我是怎么找到这个的？

当我仔细观察这些模式时，我发现了两件事。

  1. 第一个接受超过 1 个 a 和 b {1,}。所以总会有a序列和b序列并排。像 aaaabb、aabbbbb 等。但在第二种模式中，a 和 be 将与单个实例并排。比如ab、ababab、abababab等。
  2. c 在 a 序列和 b 序列之后仅出现 1 次。但在第二种模式中，c 可以出现尽可能多的次数。
于 2012-01-22T14:22:45.837 回答
0

它们是不同的，这很容易通过量词来判断。对于第一个匹配任何内容的表达式，它必须包含一个c. 第二个显然可以没有c. （还有更多差异，但这应该可以帮助您入门）。

于 2012-01-22T14:36:09.640 回答
-1

((ab)^^c^)^=(a^b^c^)^ = (a+b+c)^

于 2016-08-22T04:57:50.403 回答
-5

由于这是家庭作业，我不会给你完整的答案，但我会告诉你你需要知道的关键事实：对于给定的有限状态语言，以最少状态数识别它的 DFA 是唯一的。

顺便说一句，我不相信你的教授会在不教你如何做的情况下分配这个作业。离开互联网并阅读您的讲义和/或教科书。

于 2012-01-22T16:01:57.487 回答