字母表是 {a,b},包含 ab 子串的所有串的串写正规式是( c ) A、(ab)*ab B、(a*ba*ba*)*4.b*ab* C、(ab)*ab(ab)* D、b*a*
时间: 2023-10-04 15:14:39 浏览: 55
正确的答案是 B。
我们可以按照如下的方式来分析和解释这个正则表达式:
- (ab)*:匹配任意个数的 "ab" 子串。
- ab:匹配一个 "ab" 子串。
- (a*ba*ba*)*:匹配任意个数的 "ab" 子串,每个 "ab" 子串都可以由任意个数的 "a" 和 "b" 组成,而且中间有一个 "b"。这个子表达式的意思是可以匹配以下任意一个子串:a、ab、abb、abbb、aabb、aabbb、aaabb、aaaabb、aaaabbb、aaaaabb、aaaaabbb、等等。
- 4:指定前面的子表达式 "(a*ba*ba*)*" 必须重复出现 4 次,也就是说必须匹配 4 个 "ab" 子串。
- .:匹配任意一个字符。
- b:匹配字符 "b"。
- ab*:匹配 "a" 后面跟任意个数的 "b",也就是说可以匹配以下任意一个子串:a、ab、abb、abbb、abbbb、abbbbb、等等。
因此,这个正则表达式可以匹配的字符串包括以下几类:
- 一个 "ab" 子串。
- 重复出现 4 次的 "ab" 子串。
- 任意个数的重复出现 4 次的 "ab" 子串,中间可以插入任意字符。
- 以 "a" 开头,后面跟任意个数的 "b"。
其中,第 3 类字符串可以通过在任意两个 "ab" 子串中间插入 ".b" 来构造。
相关问题
字母表是 {a,b},包含 ab 子串的所有串的串写正规式是( b ) A、(ab)*ab B、(a*ba*ba*)*4.b*ab* C、(ab)*ab(
正确答案是 B、(ab)*ab。
首先,我们来看选项 A:(b)。这个正则表达式只能匹配单个字符 b,而不是包含 ab 子串的所有串。因此,选项 A 是错误的。
接下来,我们看选项 C:(ab)*ab(ab)*。这个正则表达式可以匹配所有包含 ab 子串的串,但它还会匹配一些不包含 ab 子串的串,比如 aab。因此,选项 C 也是错误的。
最后,我们看选项 B:(ab)*ab。这个正则表达式可以匹配所有包含 ab 子串的串,并且不会匹配任何不包含 ab 子串的串。因此,选项 B 是正确的答案。
证明正规式 (a*b*)*=(a|b)* 是等价的
正规式 `(a*b*)*` 和 `(a|b)*` 是等价的。下面是证明:
首先,我们证明 `(a*b*)*` 包含于 `(a|b)*` :
假设一个字符串 `s` 属于 `(a*b*)*`,那么 `s` 可以被表示为 `(a*b*)*` 的形式,其中 `a` 和 `b` 是任意的字符串。我们可以将 `s` 分解为多个子串,每个子串都是 `a` 和 `b` 的组合。由于 `a` 和 `b` 是任意的字符串,所以 `s` 可以包含任意数量的 `a` 和 `b`,也就是说 `s` 属于 `(a|b)*`。
接下来,我们证明 `(a|b)*` 包含于 `(a*b*)*` :
假设一个字符串 `s` 属于 `(a|b)*`,那么 `s` 可以被表示为 `(a|b)*` 的形式,其中 `a` 和 `b` 是任意的字符串。我们可以将 `s` 分解为多个子串,每个子串都是 `a` 或者 `b`。由于 `a` 和 `b` 是任意的字符串,所以 `s` 可以包含任意数量的 `a` 和 `b`,也就是说 `s` 属于 `(a*b*)*`。
因此,我们可以得出结论,正规式 `(a*b*)*` 和 `(a|b)*` 是等价的。