Finite-State Automaton

Question

I have been given the following assignment in a discrete mathematics course:

A simplified telephone switching system allows the following strings as legal telephone numbers:
a. a string of seven digits in which neither of the first two digits are a 0 or a 1.
b. A 1 followed by a three-digit area code string (any digit except 0 or 1 followed by a 0 or 1 followed by any digit) followed by a seven digit local call string.
c. A 0 alone or followed by a three-digit area code string plus a seven-digit call string.

Design a finite-state automaton to recognize all the legal telephone numbers in a, b, and c. Include an "error state" for invalid phone numbers.

I did really well with the more simple finite-state automaton drawings, but in this example, I cannot really understand even how to begin thinking about the states and inputs. In all of the examples that I have seen, there have always been two options from each state (fx, (a or b) or (0 or 1). Should I start by having each digit be a state, and then a zero meaning it's not pressed, and a one meaning it's pressed? How do I determine the length of the call string? Any help getting started is appreciated.

Answer 1

A general finite state automaton has a finite number of options from each state, not limited to two options. The options leading out of each state are labelled one-to-one by a set of symbols.

In your automaton, one sensible way to construct the automaton is to have ten options leading out of each state, labelled one-to-one by the digits $0,1,2,3,4,5,6,7,8,9$. Another way is to allow an additional "blank" symbol which when encountered means that's the end of the phone number; this is a standard way to determine the length of the call string.

So no, the digits are not the states. Instead, the digits are the options leading from each state. More generally, the "alphabet" of symbols used in the string are the options leading from each state.

Let me get you started by constructing part of the automaton, beginning with the start state, and using the eleven symbols $0,1,2,3,4,5,6,7,8,9$,"blank".

From the start state, the automaton reads the first digit.

If the first digit is $2,3,4,5,6,7,8,9$, each of those eight options leads from the start state to the "second digit of a seven digit phone number" state (notice what I did here, I gave a colloquial name to the state, to help me remember its meaning). From the "second digit of a seven digit phone number" state, the automaton reads the second digit. If the second digit is $0$, $1$, or "blank", then each of those three options leads to the error state. Otherwise, if the second digit is $2,3,4,5,6,7,8,9$, then each of those eight options leads to the "third digit of a seven digit phone number" state. Next the automaton reads the third digit: all ten options $0,1,2,3,4,5,6,7,8,0$ lead to the "fourth digit of a seven digit phone number" state, and the "blank" leads to the error state. Continue in this manner, leading up to the "eighth digit of a seven digit phone number" state, and from there, if the next symbol is a "blank" that option leads to the accept state; any other other symbol leads to the error state.

What's still left to do is to construct the parts of the automaton leading from the start state when the first symbol is $0$, $1$, or "blank".

Is that enough to get you started?