Purchase Solution

Transition Diagram for Automaton

Not what you're looking for?

Ask Custom Question

Automata theory involves the study of mathematical objects called automata and the computational problems that can be solved using them. Context-free grammar provides us with mathematical techniques of building phases in a language from other blocks that are smaller. Visual structures called parse trees enable us to clearly differentiate which phrases are unique and which ones are ambiguous.

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 = {A}

F = Accepting (or final) state = {C}

The transition table for the automaton is given by the table in the attachment.

(i) Draw the corresponding transition diagram (digraph).

(ii) Provide 5 strings that are in the language generated by the automaton.

(iii) Provide 5 strings, that use the same inputs, which are not in the language generated by the automata.

(iv) Write a general statement that describes when a string is part of the language generated by the given automata and when that string is not in the language.

Purchase this Solution

Solution Summary

Response briefly explains the logic behind answer in part (iv), and it gives more than 5 strings in part (iii) that correspond to same inputs in part (ii).

Solution Preview

(i) Please refer to the attached 575778.jpg for the transition diagram (digraph).

(iv) Any string consisting of any number of x and y that ends with atleast two ys, belongs to the language generated by ...

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.

Graphs and Functions

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

Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

Solving quadratic inequalities

This quiz test you on how well you are familiar with solving quadratic inequalities.

Probability Quiz

Some questions on probability