Share
Explore BrainMass

Theory of Computation

Consider the following three languages, all subsets of Σ* where Σ={a,b}:

(1) L1 = {w l w is a word with odd number of a's}
(2) L2 = {w l w is a word that ends with a b}

(this question is asking for a word that ends with one b)

(3) L3 = {w l w is a word with even length}

From these:

(a) Construct three DFA's (deterministic finite state automata's) that recognize these three languages

(b) Construct a DFA (deterministic finite state automata) that recognizes L1 intersection L2

(c) Construct a DFA (deterministic finite state automata that recognizes L2 union L3)

Please consult the attached file for the complete problem.

Attachments

Solution Summary

Theory of Computation is applied.

$2.19