0

这是我教科书“ Introduction to theory of Computation”中的一个示例ginen。鉴于字母表∑ as{0,1}，

{w|every 0 in w is followed by atleast one 1}}

它的正则表达式显示为(01+)*. 1+仅表示 1 的单个实例。现在我理解的是，这(01+)*将意味着字符串，例如0101010101010101....如果我有一个字符串11111101 or 011111111或只有 1 这些字符串确实满足给定的条件。但是正则表达式(01+)*不会生成它们。

Secondly for `{w|w starts and ends with same symbol}` the expression is given as `0∑*0 U 1∑*1 U 0 U 1.`

据我所知，两件事的结合意味着要么是第一个，要么是第二个，或者两者兼而有之。如果我取一个字符串 011100∑*0和另一个字符串10001 1∑*1，然后取这两个0111010001的并集，则联合字符串DOESNOT以相同的符号开始和结束。这是否意味着 union 不能将两者结合或表达式不正确？

4

1 回答 1

1

1+表示“一个或多个 1”。因此，它会生成 1、11、111 等。所以正则表达式(01+)*实际上生成的字符串是“每个 0 后跟一个或多个 1，并且字符串中的第一个符号不是 1”。

获取{w|every 0 in w is followed by atleast one 1}正则表达式会略有不同。这将是1*(01+)*

在第二个问题中，您采取的是串联。01110与10001is连接0111010001。两个集合的并集是包含两个集合的所有元素的集合

于 2013-03-09T04:53:38.537 回答