DFA可以識別多少種語言？

Question

根據Sipser的「計算理論導論」：如果A是機器M接受的所有字符串的集合，我們說A是機器M的 語言並且寫L（M）= A。 M識別A ...機器可以接受多個字符串，但它總是隻識別一種語言。以及我們說M如果A = {w | M接受w}。

我猜這個問題已經被回答了，但是我想知道是否有人有任何想法，如果有什麼有趣的話我們可以說關於常規語言的子集，如果我們可以說，原始DFA可以識別它們，並且原始DFA與識別較小語言的DFA之間是否存在任何有趣關係

Answer 1

如果DFA（總是隻有一個DFA）識別的語言是有限的，則有限該語言的許多子語言（事實上，如果接受的語言由N個字符串組成，則有2^N個子語言）。

沒有有用的關係，可以從子/超級語言關係w.r.t很容易推斷。語言在喬姆斯基層次結構中落下。也就是說：一種常規語言的子語言可能是不可判定的，而一種不可判定語言的子語言可能是規則的，其間可能存在所有可能的變化。由於這個原因，在子/超語言的DFA中沒有特別巧妙的關係：並不是所有的子語言都是正規的;一些子語言的DFA比超級語言的DFA更簡單，有些子語言的DFA比超級語言的DFA更復雜。有些將具有相同的DFA，但具有不同的接受狀態集合。