Does there exist a universal finite automaton? More precisely, is there a DFA U

Question

Does there exist a universal finite automaton? More precisely, is there a DFA U such that L(U) is equal to the language L = {(D, w) | D is a DFA and w is a string that D accepts.}? In the above. (D, w) represents the encoding of the DFA D and the string w using some sensible encoding scheme, perhaps similar to the one used in the discussion of the universal Turing machine. The actual details of the encoding shouldn't matter in your solution. Note that an equivalent question is to determine if the language L is regular.

Explanation / Answer

A DFA is specified by a finite amount of data hence you can think of it as a binary string (after all encoding). So there are only countably many DFA and hence regular sets, yet for a non-empty alphabet , has uncountably many subsets. Hence there are far many non-regular sets then regular sets over any non-empty alphabet. To get an example of a non-regular set, we have to understand the what regular sets have in common.

The set L(M) = {x : M accpets x} is called the language accepted by M. E.g.

L(M1) = {x {a, b} : x has at least 2 a’s}

A language L is regular if it is of the form L(M) for some DFA M.

We will show that the class of regular languages (over a fix ) is closed under boolean combinations, concatenation and Kleene star.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.