3

The following languages over the alphabet Σ = {0, 1} are all regular:

L = { w | w is of even length and begins with 01 }

L = { w | the numbers of 1's in w is multiple of 3 }

L = { w | w does not contain the substring 10 }

I am asked to write regular expressions for these languages, but I don't know how to do so. Can anyone give me advice on how to approach these problems?

4

2 回答 2

2

这里有一些提示：

  1. 您可以使用表达式 (0 ∪ 1) 来表示“0 或 1”，并使用 (0 ∪ 1)(0 ∪ 1) 来表示“任何两个字符的字符串”。你能从这些表达式中的第二个组成所有偶数长度的正则表达式吗？然后你能看到如何从那里得到你需要的语言吗？

  2. 任何具有多个 1 且是 3 的倍数的字符串都可以细分为一堆较小的字符串，每个字符串由三个 1 和穿插的 0 组成。你能把所有的字符串都包含三个 1 吗？从那里，你能得到你需要的语言吗？

  3. 这实际上是最简单的。写出一些不包含 10 的字符串。注意到什么了吗？作为提示，您可以使用四个字符来执行此操作。

希望这可以帮助！

于 2013-10-28T19:01:22.690 回答
1

L = { w | w 是偶数长度并以 01 开始 }

答： 01((0 + 1)(0 + 1))*

解释：01偶数长度的自身为，我们可以为任意偶数长度的字符串加上0s和1s组成的后缀。

L = { w | w 中 1 的个数是 3 的倍数}

答： (0*10*10*10*)*

说明：0可以在字符串中的任意位置出现任意次数，限制超过1它应该是 3 的倍数，所以*超过 3 1。

L = { w | w 不包含子字符串 10 }

答： 0*1*

说明：字符串不能包含10仅1表示 any 之后的 allow 1。

于 2013-10-29T14:46:34.710 回答