Section Finite State Acceptors
Unfortunately many customers using the Peanut/Dorito machine in Figure 9.4 machine could not follow instructions and had no access to a FST. They would insert coins before making a request, or try to make two purchases in one transaction. Often the machine would not give the intended output or would do nothing. It would get a hard kick, and would do nothing from then on. The Tater-Head-Ted's Snack Company that designed the machine was facing bankruptcy.
Problem 9.12.
Review the instructions 1, 2, 3 for the Peanut/Dorito machine in Figure 9.4 and make a list of all different input sequences that comply with those instructions.
Problem 9.13.
Seeing the growing evidence of expertise in graph theory on your résumé, the Company has hired you to help. What the Company needs is a separate finite state machine \(M_2\) that will answer the question, “Does the user's sequence of button pushes comply with the instructions?” This machine will have no outputs, but will have a start state \(s\) and will halt in a special state \(y\) if the answer is \(Yes\) and in some other state if it is \(No\text{.}\) (For example, input “PqhR” halts in state \(y\) and input “DPhhhR” halts in some other state.) Draw a transition diagram for this finite state machine.
With this help, the company can now automate the checking process by combining \(M_1\) and \(M_2\) into one vending machine. The new machine will save the user's input sequence in memory. When the user presses “RETURN”, it will feed a copy of the input sequence to \(M_2\text{.}\) If \(M_2\) halts in state \(y\text{,}\) it will then feed a copy of the input sequence to \(M_1\text{.}\) If \(M_2\) halts in state \(n\text{,}\) it will display the message, “Invalid input. Please try again!”.
The finite state machine \(M_2\) you constructed in Problem 9.13 is not an FST. Rather than exchanging input for output, as an FST does, its purpose is to answer the question: “Did the user give one of the valid inputs specified by the instructions?” Alternately, the question could be phrased as, “Did the user input one of the strings in Problem Problem 9.12?” Thus \(M_2\) is an example of a different kind of finite state machine that we will now describe.
Definition 9.14.
A finite state acceptor (abbreviated as \(FSA\)) is a quintuple \(\dsp M = \big( \Sigma, Q, s, Y, \delta \big)\) where
\(\Sigma\) is a finite set of symbols, called the input alphabet of \(M\text{,}\)
\(Q\) is a finite set, the internal states of \(M\text{,}\)
\(s\in Q\) is called the initial state of \(M\text{,}\)
\(Y\) is a subset of \(Q\) called the accepting states of \(M\text{,}\) and
\(\delta: Q\times\Sigma \to Q\) is called the state transition function of \(M\text{.}\)
The FSA \(M\) can be thought of as a FST that answers a Yes-or-No question. As a result, it needs no output symbols because it conveys its answer by the choice of halting state it chooses. If we interpret the input \(w \in \Sigma^*\) as a question, then the answer is “Yes” if \(M\) starting in state \(s\text{,}\) ends in a state of~\(Y\text{.}\) Otherwise the answer is “NO”. Like a FST, the transition diagram of a FSA is a labeled directed graph. The vertices of the graph are the states of \(Q\text{,}\) and there is a labeled arrow for each state \(q\in Q\) and each symbol \(a\in \Sigma\text{.}\) If the FSA \(M\) reads input symbol \(a\) while in state \(q\text{,}\) it will go into state \(r = \delta(a,q)\in Q\) and then read the next input symbol. We illustrate this fact with the follwoing transition diagram.
We would like to extend the transition function \(\delta\) to the function
where \(\Delta(q,w)\) is the state that \(M\) would reach if it were to start in state \(q\in Q\) and read the string \(w\in \Sigma^*\) from left to right. We can define \(\Delta\) by recursion on the length of \(w\) as follows.
\(\Delta(q,\lambda)=q\) and \(\Delta(q,a)= \delta(q,a)\) for \(a\in \Sigma\text{,}\)
\(\Delta(q,au) =\Delta(\delta(q,a),u)\) for \(a\in \Sigma\text{,}\) \(u\in \Sigma^*\text{.}\)
For example, let \(abc \in \Sigma^*\) and let \(q_1 \in Q\text{.}\) Define \(q_2 := \delta(a,q_1)\text{,}\) \(q_3 := \delta(b,q_2)\) and \(q_4 := \delta(c,q_3)\text{.}\) If \(M\) starts in state \(q_1\) and reads \(abc\text{,}\) it will end in state
Definition 9.16.
Given a FSA \(\dsp M = \big( \Sigma, Q, s, Y, \delta \big)\) and a string \(w \in \Sigma^*\text{,}\) we say that \(M\) accepts the string \(w\) if \(\Delta(s,w)\in Y\text{.}\) We call \(Y\) the set of accepting states.
As we do with FSTs, we illustrate a FSA as a transition diagram with its states as the vertices. We generally label the start state as \(s\) and indicate accepting states with a double circle. If \(q_4\) is an accepting state, the transitions described above would be shown in the transition diagram as
Definition 9.18.
For an alphabet \(\Sigma\text{,}\) a language over \(\Sigma\) is a subset of \(\Sigma^*\text{.}\)
Definition 9.19.
If \(M\) is an FSA, then the set
consisting of all strings accepted by \(M\) is called the language recognized by \(M\text{.}\)
For example, Problem 9.13 asked you to construct \(M_2\) to recognize the language you found in Problem 9.12. If \(L\) is the language recognized by the FSA \(M\text{,}\) then we can think of the function of \(M\) as taking any input string \(w \in \Sigma^*\text{,}\) reading \(w\) from left to right and answering the question “Are you in L?”
In practice we often find that, after reading only part of a string, we can be certain that it will not be accepted regardless of what follows. In these cases it is convenient to specify a dead state which is not in \(Y\) and cannot be exited. We will use the letter “\(z\)” to denote a dead state. Since there may be many arrows going to \(z\text{,}\) we follow the convention that all undrawn arrows are going to \(z\text{.}\)
Example 9.20.
Draw an FSA \(M_3\) that recognizes the language \(L_3\) consisting of exactly those words that contain only the letters from the input alphabet \(\Sigma = \{a,b,c\}\text{,}\) begin with \(a\) and end with \(c\text{.}\)
Problem 9.21.
Draw an FSA \(M_4\) that recognizes the language \(L_4\) consisting of exactly those words that contain the letters from the input alphabet \(\Sigma = \{a,b,c,d\}\text{,}\) begin with \(bc\text{,}\) and end with \(d\text{.}\)
Problem 9.22.
Consider the FSA \(M_5\) illustrated in Figure 9.23. Here \(s\) is the start state, \(x\) \((\)indicated with a double circle\()\) is the only accepting state, and all undrawn arrows go to the ‘dead’ state \(z\text{.}\) Let \(\Sigma = \{0,1,2\}\) and list three strings in \(\Sigma^*\) that are accepted by \(M_5\) and three strings that are not accepted by \(M_5\text{.}\)
Problem 9.24.
Draw an FSA \(M_6\) that recognizes the language \(L_6\) consisting of exactly those words that contain only the letters from the input alphabet \(\Sigma = \{a,b,c\}\text{,}\) begin with \(a\text{,}\) contain exactly one \(b\) and end with \(c\text{.}\)
Problem 9.25.
Draw an FSA \(M_7\) that recognizes the language \(L_7\) consisting of exactly those words that contain only the letters from the input alphabet \(\Sigma = \{a,b,c,d\}\text{,}\) begin with \(a\text{,}\) contain at least one \(b\) and end with \(cd\text{.}\)
Problem 9.26.
Let \(\Sigma = \{1,2,3,4\}\text{.}\) Construct an FSA \(M_8\) that will answer the question, “Does \(w \in \Sigma^*\) begin with \(12\text{,}\) contain exactly four \(3\)'s, and end with \(4\text{?}\)”
Definition 9.27.
If \(a\) is a character in our input alphabet and \(n\) is a positive integer, then \(a^n\) is the string consisting of \(a\) repeated \(n\) times. I.e. \(a^3=aaa\text{.}\)
Problem 9.28.
Are the commas in Problem 9.29 necessary?
Problem 9.29.
Construct an FSA \(M_{10}\) that recognizes the language consisting of all strings that are either
a positive power of C, followed by either an empty string or a string of As and Bs or
a positive power of D, followed by either an empty string or a string of Bs and Cs.
Problem 9.30.
Let \(\Sigma = \{a,b\}\text{.}\) Is there an FSA that will recognize the language \(L = \{a^nb^n \mid n = 1,2,3,\dots\}\text{?}\) If so, draw it. If not, why not?