1.69

2024-10-01

题目

Let . Let

a. Show that for each , no DFA can recognize with fewer than states.

b. Describe a much smaller NFA for , the complement of .

点击展开

a. Myhill–Nerode theorem 秒杀

b. NFA 刻画可能性，善于直接刻画存在性问题的故事是：对任意，第位和第位是相同字符的故事是：存在，第位和第位不同（或字符串长度不是）所以我们为每个设计一个通道，第位和第位不同时能够通向接受状态

点击展开

a. is pairwise distinguishable by L

b. 当时，构造 NFA 如下图：

NFA_1.69

是起始状态，黑圈代表拒绝状态，红圈代表接受状态。这里将本质不同的接受方式分开，稍作化简可得下图：

NFA_1.69_simplified

一般地，需要至多个状态，这远小于