Purchase Solution

Theory of Computation : Non-deterministic finite state automaton

Not what you're looking for?

Ask Custom Question

Give a non-deterministic finite state automaton that recognizes the language L subset {0,1}* that consists of all words w such that some appearance of two 0's in w is separated by an even number of 1's. (For example: the words 0010010110, 001101 are in the language but the words 0101110, 001001 are not.)

(As a note, this is the exact problem I have been asked, and can only assume that the examples of words accepted and not accepted that has been given contains a mistake, since the difference cannot be detected between the word 0010010110, and the word 001001. Ignoring the examples, is it possible to construct an accurate NFA from how it is described? I assume "some appearance" to mean all appearances for the purpose of constructing the automata.)

Then use the subset construction to convert the obtained NFA into a deterministic finite state automaton.

Please see the attached file for the complete problem description. Also, I have included copies for reference of:

1) The theorem stating the equivalence of NFA's and DFA's:
Theorem: Every nondeterministic finite automaton has an equivalent deterministic finite automaton.
2) The previous theorem's proof.
3) An example in the book, illustrating the procedure given in the above proof for converting a given NFA into a DFA.
4) An example showing the exact steps to be completed in converting a given NFA into a DFA.

I included these to help make the problem easier, and to be sure that what is being asked in this problem makes sense to everyone who reads it.

Attachments
Purchase this Solution
Solution Summary

A non-deterministic finite state automaton is investigated.

Solution Preview

If I got time tomorrow, I would definitely help you figure out the DFA part. Today I really do not have enough time.

Here enclosed is the NFA. I tested on the following two ...

Purchase this Solution
Free BrainMass Quizzes
Exponential Expressions

In this quiz, you will have a chance to practice basic terminology of exponential expressions and how to evaluate them.

Know Your Linear Equations

Each question is a choice-summary multiple choice question that will present you with a linear equation and then make 4 statements about that equation. You must determine which of the 4 statements are true (if any) in regards to the equation.

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.

Probability Quiz

Some questions on probability

View More Free Quizzes
Related BrainMass Solutions

  • Theory of Computation

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

  • Strings recognized by deterministic finite-state automaton

    60216 Determine which of the given strings are recognized by the given deterministic finite-state automaton.

  • Converting a regular expression to a DFA

    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.

  • Two Dimensional Finite Automation

    120804 Two Dimensional Finite Automaton 1. Define two dimensional finite automaton (2DIM-DFA) is defined as follows. The input is an m X n rectangle, for any m, n  2.

  • Transition Diagram for Automaton

    A finite-state automaton is given by the 5-tuple (Q, ∑, δ, q, F), where Q = the finite set of states = {A, B, C} ∑ = the Alphabet (inputs) = {x, y} δ = the transition function using the alphabet as inputs to the states q = the initial state

  • Finite State Machine

    12742 Finite State Machine Finite State Machine A finite state machine (FSM) is either deterministic or non-deterministic. A deterministic FSM (DFSM) is a FSM with at most one transition for each symbol and state.

  • Automatons

    15799 It is dealing with finite automatons (a)For each of the following languages over the unary alphabet {a}, construct a finite automaton accepting it. i. {a^2} ii.

  • Theory of computation

    Summary :- In theory of computation, the halting problem is considered to be a decision problem, in which it is analyzed that whether a turing machine computation will ever terminate, when a set of finite input is provided.

  • Testing for Useless States in Pushdown Automata

    113155 Testing for Useless States in Pushdown Automata A useless state in a pushdown automaton is never entered on any input string. Consider the problem of testing whether a pushdown automaton has any useless states.

View More Related Solutions