Operational models are based on the concept of a state and of means to represent its evolution. They are based on the concept of time and are used to describe the functioning of a system. An example of operational model is the finite state machine (or automata).
A finite state machine (FSM) is a mathematical model of computation. It is an abstract machine that can be in one of a finite number of states at any given time. The FSM can change from one state to another in response to some inputs; the change from one state to another is called a transition.
For example, a light switch is a finite state machine: the two states are ON and OFF, and the transition is the action of flipping the switch.
graph LR ON((On)) -- T --> OFF((Off)) OFF -- T --> ON
Definition
A finite state machine is defined as:
where
is the finite set of states, is the finite set of inputs, and is the transition function (generally is a partial function).
A FSM can be used for different purposes, such as:
Automata as Language Recognizers
An automaton can be used to recognize a language, i.e. to decide if a string
graph LR A(((q0))) B((q1)) start -.-> A A -- 0 --> A A -- 1 --> B -- 0 --> B -- 1 --> A
where the state
Definition
Move sequence for an input string (not just one symbol) is a sequence of states that starts from the initial state and follows the transitions according to the input string. The move sequence is accepting if it ends in a final state.
where
is defined inductively from , by induction on the string length:
The initial state is
, the set of final states is , and the accepting move sequence is:
Automata as Language Translators
An automaton can be used to translate a language, i.e. to transform a string
graph LR A(((q0))) B((q1)) start --> A A -- 1/11 --> A A -- 0/ɛ --> B -- 1/11 --> B -- 0/0 --> A
so, given the string
Definition
A translation
is a function that maps a string in a language into a string in a language . It is defined by a finite state machine that recognizes the translation:
where:
is the finite set of states is the finite set of inputs is the transition function (is the same partial function as for the language recognizer) is the initial state is the set of final states is the output alphabet is the output (translation) function that maps a state and an input to an output string
The
Definition
The translation move is defined as:
Meaning that the translation of a string
is the output of the move sequence of the string if the move sequence is accepting.
Finite State Machine
A finite state machine is a very simple, intuitive model, applied in various applicative domains, also outside Computer Science. The analysis of a finite state machine can be done by:
- Simulation: the machine is run on a given input string, and the move sequence is observed.
- Verification: the machine is analyzed to determine if it recognizes the desired language or performs the desired translation.
- Synthesis: the machine is constructed to recognize a given language or perform a given translation.
- Optimization: the machine is analyzed to determine if it can be simplified.
Cycles
In the context of finite automata, cycles are important structures that allow for repeated processing of input symbols.
The following diagram illustrates the transitions between states in an automaton:
graph LR q0((q0)) -- b --> q1((q1)) -- a --> q2((q2)) -- b --> q9(((q9))) q1 -- b --> q7((q7)) q2 -- a --> q3((q3)) -- b --> q6((q6)) -- a -->q4((q4)) -- b --> q1 q4 -- a --> q5((q5)) q9 -- b --> q7 q9 -- a --> q8(((q8)))
In this automaton, there exists a specific cycle: starting from state
The cycle allows the automaton to process the sequence
-
Repetition of Input: When the automaton encounters the input sequence that leads it into this cycle, it can process that sequence multiple times.
For example, once the automaton transitions through the states
to and back to , it can repeat this process indefinitely. This means it can handle strings of the form where the sequence can be followed by additional occurrences of the same cycle. -
Formal Language Representation: In terms of formal languages, this means that any string that falls into the cycle can be described using regular expressions.
For instance, the cycle contributes to a language defined by the expression
, where and are non-negative integers. The string can have varying lengths depending on how many times the cycle is traversed. -
Implications for State Transitions: The existence of a cycle has significant implications for the design of finite automata, particularly when considering state transitions. The automaton can accept a wider variety of strings, as it can adjust the number of cycles it traverses based on the input.
-
Indefinite Repetition: Importantly, because the cycle can be traversed multiple times, it demonstrates the automaton’s capability to process infinitely many strings, provided they fit the structure dictated by the cycle. This feature is critical in applications like lexical analysis in compilers and pattern matching.
Pumping Lemma
The Pumping Lemma is a fundamental concept in the theory of formal languages and automata. It provides a necessary condition for a language to be regular, meaning that it can be recognized by a finite state automaton.
Pumping Lemma
If a string
belongs to a language and the length of is greater than the number of states in the automaton (i.e., ), then the automaton must exhibit a cycle. This means that there exists a state and a string such that the string can be expressed in the form , where:
is the portion of the string leading to state , is the part that causes the cycle, is the part following the cycle. In formal terms, this implies that
, where denotes the state transition function applied to the string . Consequently, for any non-negative integer , the string will also be in . This condition must hold for all strings in the language that are longer than the number of states in the automaton.
Property
For an automaton
with language , the properties of the language can be summarized as follows:
Infinite Language:
if and only if there exists a cycle in the transition graph that includes a node along a path from the initial state to at least one final state . This indicates that the automaton can repeat certain transitions indefinitely, generating an infinite number of strings. Empty Language:
if and only if there exists a string such that there is no string with length . This implies that if a string exists in the language, it must be longer than the number of states in the automaton; thus, the language cannot be recognized by any finite state machine if it contains short strings.
Applications of the Pumping Lemma
To illustrate the pumping lemma’s application, consider the language
To demonstrate that this language is not recognized by any finite state machine, assume for contradiction that a string
belongs to , where . Applying the pumping lemma, we express as with representing the cyclic segment. We can analyze three possible cases for :
Case 1:
where (with ): This leads to strings of the form for all . However, this contradicts the requirement that the number of ‘s must equal the number of ‘s. Case 2:
where (with ): This results in strings for all , which similarly violates the balance between ‘s and ‘s. Case 3:
where (with ): This gives rise to strings of the form for all , which again leads to an imbalance in the number of ‘s and ‘s.
It’s essential to note that while all computers can be considered finite state machines in terms of their state transitions, they often operate with an effectively infinite memory capacity, as they can handle and manipulate strings that comfortably fit within their finite storage limits. Thus, the capabilities of finite state machines are strictly limited compared to computational models that can utilize infinite memory, such as Turing machines.
Closure Properties of Regular Languages
In formal language theory, closure refers to the property of a set of languages remaining within the same family of languages after the application of certain operations. More specifically,
Definition
A family of languages
is said to be closed under a binary operation (such as union, intersection, difference, concatenation, etc.) if applying the operation to any two languages within results in a language that is still in . Formally, we say that:
Definition
The set
is defined as the family of regular languages, which are languages that can be recognized by a finite state automaton (FSA).
One of the key features of regular languages is their closure under several common operations, which makes them a robust class of languages in automata theory. Regular languages are closed under the following set-theoretic operations:
- Union: If
and are regular, then is also regular. This means that we can construct a finite automaton that recognizes strings belonging to either or . - Intersection: If
and are regular, then is also regular. This follows from the fact that finite automata can be combined to simultaneously recognize strings in both languages. - Difference: If
and are regular, then (the set of strings in but not in ) is regular. This can be achieved by constructing automata that recognize and use the complement of . - Complement: If
is regular, then its complement is regular. This is because finite state automata can be easily modified to recognize the complement by swapping accepting and non-accepting states.
In addition to set-theoretic operations, regular languages are closed under several other important operations:
- Concatenation: If
and are regular, then is also regular. Finite state automata can be constructed to recognize concatenations by modifying the transition functions accordingly. - Kleene Star (Closure): If
is regular, then the Kleene star , which represents the set of all strings formed by concatenating zero or more strings from , is regular. This operation reflects the ability to repeat a language an arbitrary number of times. - Positive Closure: If
is regular, then is also regular. This is similar to the Kleene star but excludes the empty string.
Intersection of Automata
When dealing with finite automata, the intersection of two automata
Definition
Given two automata:
The intersection automaton
is constructed as follows:
- State set: The states of the intersection automaton are the Cartesian product
, meaning each state in the new automaton is a pair where and . - Input alphabet: The input alphabet
remains the same for both automata. - Transition function: The transition function
is defined as . This means that both automata transition simultaneously, and the new state depends on both transitions. - Start state: The start state of the new automaton is
, the pair of start states from the original automata. - Final states: The set of final states is
, meaning a state is accepting if both and . Using this construction, we can prove by induction that:
This means the new automaton accepts exactly the strings that are accepted by both original automata.
Example
Consider two automata with the following transitions:
graph LR q0((q0)) -- b --> q1((q1)) -- a --> q2(((q2))) -- a --> q9(((q3))) p0((p0)) -- b --> p1((p1)) -- a --> p2((p2)) -- a --> p9(((p3)))The intersection automaton can be constructed as:
graph LR q0p0((q0p0)) -- b --> q1p1((q1p1)) -- a --> q2p2((q2p2)) -- a --> q9p9(((q3p3)))This automaton accepts strings that both automata accept, such as the string
.
Union of Automata
The union of two automata
However, this approach relies on computing the complement of the languages, which is not always straightforward or closed under intersection for non-deterministic automata.
For finite automata, obtaining the complement of a language
- The analysis of a string does not terminate (i.e., the automaton gets stuck in a non-final state).
- The automaton continues indefinitely, making it impossible to simply swap accepting and non-accepting states.
For finite automata (FA), the problem can be resolved by simply modifying the final states, but in more general computational models (e.g., Turing machines), this method does not necessarily work. This limitation reflects the difficulty in providing a positive answer to a complement problem if we cannot decisively determine whether a string belongs to the original language.