Strings recognized by deterministic finite-state automaton
Not what you're looking for?
Determine whether each of these strings is recognized by the given deterministic finite-state automaton (which is displayed in an attached .doc file):
(a) 010
(b) 1101
(c) 1111110
(d) 010101010
Purchase this Solution
Solution Summary
For each string, every step which is executed by the automaton (when that string is input to it) is analyzed in detail.
The results of that analysis are used to determine which of the strings are recognized by the automaton.
Solution Preview
The set of states recognized by the finite-state automaton are those that reach one of the "final" states.
The final states are those which are designated in the diagram by a pair of concentric circles (namely, s_0 and s_3).
Thus we consider what happens when each of the given strings is input to the automaton.
Regardless of the input, the automaton starts in state s_0, and it reads the bits in the input string from left to right.
----------------------------------------------------------
(a) 010
Step 1: The machine reads a 0 (the 0 on the left), and remains in state s_0 (see the "loop" in the diagram).
Step 2: The machine reads a 1, then goes from state s_0 to state s_1 (see the arrow with the "1", directed from state s_0 to state s_1).
Step 3: The machine reads a 0, then goes back to s_0 (see the arrow with the "0", directed from state s_1 to state s_0).
Since all the bits of the input string have been read, the machine ends up in state s_0, which is a final state, so the machine does recognize the ...
Education
- AB, Hood College
- PhD, The Catholic University of America
- PhD, The University of Maryland at College Park
Recent Feedback
- "Thanks for your assistance. "
- "Thank you. I understand now."
- "Super - Thank You"
- "Very clear. I appreciate your help. Thank you."
- "Great. thank you so much!"
Purchase this Solution
Free BrainMass Quizzes
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.
Multiplying Complex Numbers
This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.
Probability Quiz
Some questions on probability