Finite Automata

A finite automaton has a set of states, and its “control” moves from state to state in response to external “inputs.” One of the crucial distinctions among classes of finite automata is whether that control is “deterministic,” meaning that the automaton cannot be in more than one state at any one time, or “nondeterministic,” meaning that it may be in several states at once.

In another way, a finite automaton is like a little machine. It has different “states” it can be in, like different modes or conditions. When it gets some input, it can switch from one state to another.

There are two types of these machines:

1. Deterministic: This type of machine can only be in one state at a time, like flipping a light switch on or off. It can’t be in multiple states simultaneously.
2. Nondeterministic: This type of machine can be in more than one state at once, like having multiple apps open on your computer screen at the same time.

In a nutshell, deterministic machines are like single-taskers, while nondeterministic ones are multitaskers.

An Informal Picture of Finite Automata with Real-life Examples

Here I have put an extended example of a real-world problem whose solution uses finite automata in an important role.

Here we have investigated protocols that support “electronic money” — files that a customer can use to pay for goods on the internet and that the seller can receive with assurance that the “money” is real.

The seller must know that the file has not been forged, nor has it been copied and sent to the seller, while the customer retains a copy of the same file to spend again.

The nonforgeability of the file is something that must be assured by a bank and by a cryptography policy. That is, a third player, the bank, must issue and encrypt the “money” files, so that forgery is not a problem.

However, the bank has a second important job: it must keep a database of all the valid money that it has issued so that it can verify to a store that the file it has received represents real money and can be credited to the store’s account.

The Ground Rules electronic money

There are three participants: the customer, the store, and the bank. We assume for simplicity that there is only one “money” file in existence.

The customer may decide to transfer this money file to the store, which will then redeem the file from the bank (i.e., get the bank to issue a new money file belonging to the store rather than the customer) and ship goods to the customer.

In addition, the customer has the option to cancel the file. That is, the customer may ask the bank to place the money back in the customer’s account, making the money no longer spendable. Interaction among the three participants is thus limited to five events:

• The customer may decide to pay. That is, the customer sends the money to the store.
• The customer may decide to cancel. The money is sent to the bank with a message that the value of the money is to be added to the customer’s bank account.
• The store may ship goods to the customer.
• The store may redeem the money. That is, the money is sent to the bank with a request that its value be given to the store.
• The bank may transfer the money by creating a new, suitably encrypted money file and sending it to the store.

The Protocol for Electronic Money

The three participants must design their behaviors carefully, or the wrong things may happen. In our example, we make the reasonable assumption that the customer cannot be relied upon to act responsibly. In particular, the customer may try to copy the money file, use it to pay several times, or both pay and cancel the money, thus getting the goods “for free.”

The bank must behave responsibly, or it cannot be a bank. In particular, it must make sure that two stores cannot both redeem the same money file, and it must not allow money to be both canceled and redeemed. The store should be careful as well. In particular, it should not ship goods until it is sure it has been given valid money for the goods.

Protocols of this type can be represented as finite automata. Each state represents a situation that one of the participants could be in. That is, the state “remembers” that certain important events have happened and that others have not yet happened. Transitions between states occur when one of the five events described above occurs. We shall think of these events as “external” to the automata representing the three participants, even though each participant is responsible for initiating one or more of the events. It turns out that what is important about the problem is what sequences of events can happen, not who is allowed to initiate them.

Figure 1 represents the three participants by automata. In that diagram, we show only the events that affect a participant. For example, the action pay affects only the customer and store. The bank does not know that the money has been sent by the customer to the store; it discovers that fact only when the store executes the action redeem.

Let us examine first the automaton (c) for the bank. The start state is state 1; it represents the situation where the bank has issued the money file in question but has not been requested either to redeem it or to cancel it. If a cancel request is sent to the bank by the customer, then the bank restores the money to the customer’s account and enters state 2. The latter state represents the situation where the money has been canceled. The bank, being responsible, will not leave state 2 once it is entered, since the bank must not allow the same money to be canceled again or spent by the customer.

Below you can see the explanation of Finite automata representing a customer, a store, and a bank

Bank’s Actions (Bank Automaton):

1. Start State (State 1): This is where the bank begins. It means the bank has issued the digital money but hasn’t received any special requests yet.
2. State 2: If the customer asks the bank to cancel the money, the bank goes to this state. The money is canceled, and the bank makes sure it can’t be used again.
3. State 3: If the bank receives a request from the store to redeem the money, it goes to this state. It then sends the store a new money file that now belongs to the store. After sending it, the bank goes to State 4. In State 4, the bank won’t do anything else related to this particular money file. It’s like the bank’s job is done for this money file.

Store’s Actions (Store Automaton):

1. Start State (State a): The store begins here. It’s ready to receive orders from customers.
2. State b: When a customer orders goods and pays for them, the store goes to this state. It starts handling both shipping and redeeming the money.
3. State c: If the store ships the goods first, it enters this state. In this state, the store still needs to redeem the money from the bank and receive a new money file from the bank.
4. State d: If the store sends a redeem request to the bank first, it enters this state. From here, it might either ship the goods (going to State c) or receive the new money file from the bank (going to State f).
5. State e: If the store ends up in this state, it’s waiting for the new money file from the bank. Unfortunately, the goods have already been shipped, and if the new money file doesn’t arrive, the store faces a problem.
6. State f: If the store gets the new money file from the bank, it enters this state. At this point, we expect the store to eventually ship the goods, and then the transaction is complete (State g).

Customer’s Actions (Customer Automaton):

1. Customer’s State: The customer has only one state. This means the customer can do anything, like order goods, pay, cancel payments, and repeat these actions in any order. After each action, the customer stays in the same state.

In simple terms, these automata represent how the bank, store, and customer handle digital money transactions. The bank ensures the money is used securely, the store manages orders and payments (with some possible pitfalls), and the customer can do various actions without restrictions.

Complete Enabling the Automata to Ignore Actions

Imagine we have three participants in a digital money system: the customer, the store, and the bank. Each of them has a set of actions they can take.

First Issue – Missing Actions:

1. Sometimes, there are actions that should not make a participant “break” or stop functioning. For example, if the customer decides to cancel a payment, it shouldn’t cause the store to stop working altogether. But in the formal rules of these systems, every action should lead to something happening. So, to fix this, we add a special action called “cancel” that lets the store stay in the same state it’s in, without breaking.
2. Another problem is when a participant gets an unexpected action. For instance, if the customer tries to pay again when the store is in a specific state, it should not cause the store to stop working. So, we add extra actions to each participant’s set of actions to prevent this from happening. These extra actions allow the participant to stay in the same state and not “break.”

Second Issue – Ignoring Actions:

1. Some actions are not important for certain participants. For example, the store doesn’t care about the “cancel” action, so we add a way for the store to ignore it without causing any problems. The bank doesn’t need to worry about “pay” or “ship” actions, so it also ignores them.
2. The customer, on the other hand, doesn’t really affect the system’s behavior. It can do actions like “ship,” “redeem,” and “transfer,” but these don’t change the overall operation of the system. The customer mainly initiates “pay” and “cancel” actions, but its actions don’t affect how the system works as a whole.

In simple terms, we add some special actions and rules to make sure that the participants in the digital money system don’t “break” when they receive unexpected actions and that they can safely ignore actions that don’t concern them. This helps keep the whole system running smoothly and avoids any unexpected hiccups.

Complete the Entire System as an Automaton

1. Missing Interaction Model:
Imagine three participants – a customer, a store, and a bank – in a digital money system. We know how each of them behaves separately, but we don’t yet understand how they interact or work together. The customer can do anything without restrictions, so it has just one state. But the store and the bank are more complicated.

2. Constructing the Product Automaton:
To figure out how the store and the bank interact, we create something called a “product automaton.” This automaton has states that represent pairs of states, one from the store and one from the bank. For example, the state (3, d) means the bank is in state 3, and the store is in state d. Since the bank has four states and the store has seven, the product automaton has 4 x 7 = 28 states.

3. Defining State Transitions:
To decide how this product automaton should work, we need to look at how the bank and store react to different actions. We must make sure that if an action is received, both the bank and the store have somewhere to go (a state to transition to).

4. Selecting Arcs:
We choose the connections between states (arcs) based on the actions. For example, if the customer pays, the store goes from state a to b. But if the store is in any other state, it stays put. Similarly, if the bank receives a redeem message while in state 1, it goes to state 3. But in state 2, the bank “dies” because it can’t respond to a redeem request.

5. Insights from the Automaton:
Looking at the product automaton, we can see that not all states are reachable from the start state (1,a), which is where everything begins. Some states, like (2,e) or (4,d), cannot be reached at all. This means they don’t need to be included in the automaton.

6. Purpose of Analysis:
The main reason we use these automata is to answer questions about potential errors in the system. For instance, we might ask if it’s possible for the store to ship goods and never get paid. By analyzing the automaton, we can check if there’s a state where the store has shipped goods (state in column c, e, or g) but no transition for payment (input T) has ever occurred. We can reason through the automaton to find out if such errors are possible.

7. Example of Error:
For example, state (3,e) is not a problem because eventually, there will be a transition on input T, meaning the bank will transfer the money to the store. However, state (2,¢) is problematic. It represents a situation where the bank received a cancel message before a redeem message, but the store also received a payment message. In this case, the store shipped goods before trying to redeem the money. When the store finally tries to redeem the money, the bank won’t acknowledge it because it’s in a state where it has canceled the money and won’t process a redeem request.

In a nutshell, this process helps us understand how the different participants in a digital money system interact and how to spot potential errors or problems in the system’s behavior.