Discrete Mathmatics_Help

Task Background

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.

Task Assignment: Below you will find a question the areas of automata. Solve the problem showing all steps. Thoroughly explain how and why you performed each step with complete sentences.

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:

Question 1:  Draw the corresponding transition diagram (digraph).