【计算理论导引】 课后习题1.48

题干

设 Σ={0,1}\Sigma=\{0,1\}Σ={0,1} 以及
D={w∣w中子串01与10的出现次数相等}, D=\{w|w中子串01与10的出现次数相等\}, D={w∣w中子串01与10的出现次数相等},

由于 $101$ 含有一个 $01$ 和一个 $10$，因此 $101\in D$。而 $1010$ 含有两个 $10$ 和一个 $01$，所以 $1010\notin D$。证明： $D$ 是正则语言。

分析

若D是正则语言，那么必然存在一个DFA ，其语言是D，等价于存在正则表达式R，使得L(R)=D。如果能够构造识别D的正则表达式，那么就证明了D是正则语言。

从子串 10 和 子串 01 的性质入手。观察到某个字符串中出现这两个子串当且仅当在从左向右扫描字符串的过程中字符发生变化。以字符串 111001011 为例，从左向右扫描的过程中字符串变化了4次，更加细致地说，由 1 变化到 0 两次，由 0 变化到 1 两次，分别对应了两个 10 子串和两个 01 子串。

换一个角度来看，我们把字符串看作连续的若干个 1 组成的子串和连续的若干个 0 组成的子串的交替排列，10 子串和 01 子串数量相等的充分必要条件为这样的连续若干个 1 组成的子串和这样的连续若干个 0 组成的子串的数目相同相差 $1$。

写为正则表达式的形式如下
$$R=((1^{+}{0}^{+}{)}^{\ast }{1}^{+})\cup ((0^{+}{1}^{+}{)}^{\ast }{0}^{+}).$$

证明

如分析，证毕。$■$