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.
|
|
δ
|
δ
|
|
|
x
|
y
|
|
A
|
A
|
B
|
|
B
|
A
|
C
|
|
C
|
A
|
C
|
(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.