Purchase Solution

Theory of Computation

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution

Solution Summary

The theory of computation is applied. An deterministic finite state for automata that recognize these three languages is determined.

Purchase this Solution


Free BrainMass Quizzes
C++ Operators

This quiz tests a student's knowledge about C++ operators.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

C# variables and classes

This quiz contains questions about C# classes and variables.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.