Purchase Solution

Converting a regular expression to a DFA

Not what you're looking for?

Ask Custom Question

How can a regular expression be converted into a deterministic finite automaton (DFA)?

Purchase this Solution
Solution Summary

This solution walks through the steps of converting a regular expression to a DFA.

Solution Preview

The basic approach to convert a regular expression to a DFA is to first convert the regular expression an an NFA (non-deterministic finite automaton) and then convert the NFA to a DFA. Doing this breaks the problem down into a couple of manageable states.

An NFA differs from a DFA in that there are "epsilon" states which are transitions between states with no input. There are also multiple transitions from one state to another on the same input.

In order to convert the regular expression to an NFA we use the following five rules:

1) any literal becomes an NFA that goes from the start state to final state, transitioning on the input. That is, a literal "a" in the regular expression becomes an NFA like this:

<pre>
(start) ----[a]----> (final)
</pre>

2) any "epsilon" in the regular expression (that is a zero length string) becomes the NFA:

<pre>
(start) ...

Purchase this Solution
Free BrainMass Quizzes
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.

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.

Basic Networking Questions

This quiz consists of some basic networking questions.

Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.

C++ Operators

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

View More Free Quizzes
Related BrainMass Solutions

  • Theory of Computation : Non-deterministic finite state automaton

    a given NFA into a DFA. 4) An example showing the exact steps to be completed in converting a given NFA into a DFA.

  • Automata and Computability

    So, we can obtain a DFA D' for NOEXTEND(A) by removing from the set F all states from which there are non-empty path to other states in F; otherwise D' is identical to D. The expert examines automata and cinoutability for NOPREFIX.

  • 2DIM-DFA is undecidable

    We will reduce ELBA to EQ-2DIM-DFA by showing that if EQ-2DIM-DFA is decidable than so is ELBA. We first show how to encode the computation history of a LBA using a rectangle.

  • Two Dimensional Finite Automation

    We will reduce ELBA to EQ-2DIM-DFA by showing that if EQ-2DIM-DFA is decidable than so is ELBA. We first show how to encode the computation history of a LBA using a rectangle.

  • Theory of Computation

    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

  • Algebraic excercises Related to exponents and radicals

    Problem 15 a) b) c) d) Problem 16 Solution a) b) When h=0, The solution describes the steps in converting radicals to exponents form and vice versa.

  • Converting Infix to Postfix with C++

    243975 Converting Infix to Postfix with C++ For every postfix expression there exists a corresponding and uniquely defined infix expression that evaluates to the same number. The converse is not true.

  • Conversion Program

    256154 C++ program that converts roman numeral to regular number I need help creating a c++ program that converts roman numerals to regular numbers. it needs to be simple and done using just if statements.

  • Converting word problem to algebraic expression

    349105 Converting word problem to algebraic expression 1.) Write the following as an algebraic expression using x as the variable : the sum of a number and -8 2.)

View More Related Solutions