Adjustments to an automaton. Show that the intersection of two sets of languages

Question

Adjustments to an automaton.

Show that the intersection of two sets of languages can be empty, finite (of arbitrarily large cardinality), countably infinite, or uncountably infinite. Which of the following modifications / restrictions to finite automata would change the class of languages accepted relative to "normal" finite automata? The ability to move the read head backwards (as well as forwards) on the input. The ability to write on (as well as read from) the input tape. Both a) and b) simultaneously. Having 2 read-heads moving (independently, left-to-right) over the input. Having one billion or less different states.

Explanation / Answer

3. Note: "?" represents intersection of two sets of languages, and Q represents set of rational numbers(Q is countable), R is the set of real numbers.

   a) [0,1] ? [3,4] = phi                                                             // intersection results in empty set

   b) [0,1] ? [1,2] = {1}                                                              // finite intersection

   c) (Q U [0,1]) ? (Q U [1,2]) = Q                                           // countably infinite

   d) R ? R = R                                                                         // uncountably infinite

4. Ans: (c)

    If both the operations (a) and (b) are allowed then we end up in getting Turing Machine.

Turing Machines describes a much larger class of languages, the class of recursive enumerable languages.

Finite state machines describes the class of regular languages.

So, the class of languages accepted by finite automata changes when (c) is applied.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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