Explore BrainMass
Share

Explore BrainMass

    Transition Diagram for Automaton

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com October 10, 2019, 7:17 am ad1c9bdddf
    https://brainmass.com/math/discrete-optimization/transition-diagram-for-automaton-575778

    Attachments

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

    $2.19