时间戳

首页 > 解决方案 > 编写描述集合的正则表达式

regular-language - 编写描述集合的正则表达式

问题描述

左 {w| w 包含任意数量的子串 00 和 11，其中一个 1 出现在 w 中的任何位置}

我的猜测是，因为 1 可以在任何地方，所以 Σ*001Σ*1Σ*11Σ* 应该是正则表达式。有什么想法或更正吗？

标签： regular-languageautomaton

解决方案

将语言定义分解成几个部分：

L := { w | 
  w contains any number of substrings 00 and 11
  w contains one "1"
}

第一部分实际上没有任何意义。“任意数量的子字符串 00 和 11”可以不包含子字符串。这并不是说字符串必须至少包含其中一个。这相当于Σ*.

第二部分说字符串必须包含1在其中的某个地方：Σ*1Σ*

推荐阅读