The transition table given is:
- Transition diagram
According to the transition table, the two possible inputs are x and y. The left-most column indicates the possible state, and the row corresponding to each state represents the next state for an input of that column. The transition diagram above is a graphical representation of this; the directed lines are from the present to next state for a given input of x or y, as marked above the line. For example, when in state B (current), an input of y results in next sate as C. Here, the final accept state (denoted by two circles) is C, and the initial state is A.
- A string generated by the automation is a sequence of inputs or components of the Alphabet. A set of five strings generated by this automation – {x, y, xx, xy, yx}. For a more specific language, consider the criterion that the strings must end with y. Then a set of five strings that are recognized by this language would be {xy, xxy, xxxy, xxxxy, xxxxxy}. There could be any number of such strings that are recognized by a particular language in the automation (Booth, 1967). Now a set of five strings that begin with the state A and end in C can be can be denoted by {y, x, x, y, y}. The corresponding run for this word would then be A -> B -> A -> A -> B -> C.
- Consider the last set of 5 strings used in part 2. This belongs to a language that recognizes words that are sequenced to start from A and end in C. In other words, from the initial state, any set of inputs when carried out in sequence, and end in C, will be a subset of this language. Now using the same inputs {y, x, x, y, y}, and changing the sequence to {x, y, x, y, y} would still result in a sequence that can start in A and end in C. However, {y, x, y, x, y} is a set of the same five strings that will not be recognized by the language. This is because, starting from A, this sequence will finally end in B. Now consider the first language example where strings end in y. Then using the same inputs as above, the set containing {yx, yxx, yxxx, yxxxx, yxxxxx} will not be recognized by the language.
- A formal language recognized by automata can have rules dictated by a formal grammar, or a regular expression, or by some formal decision procedure. For instance, a language L could be defined by the rule mentioned above - a string must end in y. Then, the following general statement will be true for a string that is part of the language so generated: L:{aiy} where ai ε ∑. In words, L is a language that recognizes all strings that end in y (Hopcroft, 2007).
References
Booth, T. L. (1967). Sequential machines and automata theory (Vol. 3). New York: Wiley.
Hopcroft, J. E. (2007). Introduction to automata theory, languages, and computation. Pearson Addison Wesley.
