Explore BrainMass

Transition Diagram for Automaton

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.


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 ...

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).