A compiler plays a crucial role in the software development process by analyzing a source program to ensure its correctness. This involves a series of steps, starting with the verification of the program’s syntax and semantics. A document processor, on the other hand, performs a spell check on individual words before verifying the overall syntax of the document. Additionally, a graphical user interface (GUI) must ensure that user inputs are correctly entered, which often involves validation checks to prevent errors.
Recognition Algorithms and Automata
In the study of automata, it is important to note that they operate independently of specific programming languages and techniques. This abstraction means that the properties of automata, such as time and memory complexity, are more directly associated with the class of source languages they recognize, rather than the specific implementation details. This characteristic allows for a clearer understanding of how automata function in relation to language recognition.
To determine if a string belongs to a specific language, recognition algorithms are employed. These algorithms produce a binary output (either a “yes” or “no” response) indicating whether the string is valid.
Algorithm
The input domain for these algorithms consists of strings formed from a given alphabet, denoted as
. When a recognition algorithm , is applied to a string , the result is expressed as . If the algorithm returns “yes,” the string is accepted; otherwise, it is rejected. The set of all accepted strings by algorithm
is represented as
It is typically assumed that recognition algorithms will terminate for every input. However, there may be cases where the algorithm fails to terminate for certain strings. In such instances, the output of
It is important to recognize that even among context-free languages, some decision problems—beyond just string membership—are undecidable. This limitation is a significant consideration in the design and analysis of recognition algorithms.
Recognition of strings is merely the initial step in the compilation process. Within the realm of compilation, time complexity is often prioritized over space complexity. This emphasis on time complexity is particularly relevant in contexts where electric power consumption is a concern, such as in portable programmed devices. Efficient algorithms not only improve processing speed but also contribute to optimizing battery usage, making them vital in the design of energy-efficient systems.
A General Automaton
Definition
An automaton, or abstract machine, is a simplified theoretical model of a computer designed to execute a small set of basic instructions. The key components of an automaton include a control unit, which manages the computation by switching between a limited number of states, and an auxiliary memory that has unlimited capacity.
The auxiliary memory is distinct from the random access memory (RAM) used in modern computational models, as it operates on a tape rather than on arbitrary-access data storage.
The automaton operates on an input tape, which contains the source string that must be processed. The input tape is bordered by two delimiters:
- the start-of-text mark, represented as
, - and the end-of-text mark, or terminator, represented as
.
The string itself lies between these delimiters. Although the input tape can only be read, the automaton can modify its auxiliary memory, which consists of symbols from a separate alphabet. At each discrete time step, the automaton reads a character from the input, reads a symbol from the memory tape, and performs one or more operations: shifting the reading head, altering the memory, or changing the control unit’s state.
The automaton’s moves are determined by the current input character, the current memory symbol, and the state of the control unit. The moves might involve shifting the input head left or right, modifying the symbol in memory, moving the memory head, or transitioning to a new state in the control unit.
Definition
A machine is classified as unidirectional if its input head moves only in one direction—from left to right—across the input tape.
At any moment, the future behavior of the automaton depends on its instantaneous configuration. This configuration is a 3-tuple consisting of the input symbol currently being read, the memory symbol being accessed, and the current state of the control unit. When the automaton begins, it starts in an initial configuration: the input head is positioned at the first character (just to the right of the start-of-text mark), the control unit is in its initial state, and the memory holds a specific symbol, typically representing the beginning of the computation.
From this initial configuration, the automaton proceeds through a sequence of moves, known as a computation, which results in a series of new configurations.
A configuration is considered final when two conditions are met: the control unit reaches a state designated as final, and the input head reaches the end-of-text mark.
In some cases, a final configuration might also depend on the state of the memory tape, for example, if the tape needs to be empty or contain a specific string.
The automaton accepts the input string if its computation reaches a final configuration. The set of all strings that lead to an accepted final configuration defines the language recognized by the automaton. Conversely, a computation can also terminate if no valid moves are possible from the current configuration, even if the final configuration has not been reached.
When two automata recognize the same set of strings, meaning they accept the same language, they are considered equivalent.
This concept is central to the study of automata theory, where different machine designs or formal models may still define the same languages despite having varying internal mechanics.
Turing Machine
A Turing Machine is a theoretical model of computation that plays a fundamental role in understanding the limits and capabilities of what can be computed. The family of languages it can accept is known as recursively enumerable languages. In essence, a recursively enumerable language is one for which a Turing Machine can identify if a string belongs to the language by accepting it if it does.
However, this acceptance does not necessarily mean the machine will halt for every possible input; it may run indefinitely if a string does not belong to the language.
Theorem
A language is termed decidable or recursive if there exists a Turing Machine that not only accepts strings within the language but also halts on every possible input, regardless of whether the input is in the language.
This implies that a Turing Machine designed for a decidable language will produce a definitive result for each input—either by accepting or rejecting the string and halting. Such a machine functions as a recognizer for decidable languages, making it essential for understanding two language families in the Chomsky hierarchy of formal languages: context-free languages and context-sensitive languages.
The Chomsky hierarchy categorizes languages based on their complexity and the type of automaton that can recognize them.
- The simplest model of computation within this hierarchy is the finite automaton, which operates without any auxiliary memory beyond its finite states. A finite automaton is suitable for recognizing regular languages, which are the least complex type of languages in the Chomsky hierarchy. Regular languages are limited in their expressive power but benefit from high computational efficiency, as they can recognize strings in linear time, or real-time. In practical terms, a finite automaton can process a string with a number of steps equal to the input length, making it highly efficient for tasks where simplicity and speed are essential.
- When a form of memory, structured as a Last In, First Out (LIFO) stack, is available, the computational model becomes a pushdown automaton. This model is more powerful than a finite automaton and is capable of recognizing context-free languages. The stack memory enables the machine to handle nested structures, a characteristic feature of context-free languages. While more powerful than regular languages, context-free languages are less expressive than context-sensitive languages, and the computational complexity for recognizing context-free languages is generally bounded by a polynomial function of the input string’s length. In other words, pushdown automata can process these languages relatively efficiently, although not as fast as finite automata for regular languages.
- The Turing Machine is capable of recognizing even more complex languages, specifically context-sensitive languages, which demand greater computational resources. However, for a Turing Machine to recognize these languages, it often requires significant time, frequently resulting in non-polynomial time complexity. This high complexity makes Turing Machines unfeasible for practical applications when it comes to context-sensitive languages due to the potential for lengthy or impractical runtimes.
Introduction to Finite Automata
Finite automata represent some of the simplest and most fundamental abstract computational devices in the field of computer science.
Definition
A finite automaton operates on an input tape containing a source string
. It consists of three main components: the control unit, the reading head, and the set of states.
The reading head is initially positioned on the first character of the string
As the automaton processes the input string, it updates the state of the control unit and advances the reading head based on predefined transition rules. The automaton accepts the input string
Example: Decimal Constants
Consider the language
of decimal constants, defined over the alphabet , where includes all non-zero digits. The regular expression representing this language is given by:
This regular expression defines valid decimal constants, which may include an optional leading zero, followed by a non-empty sequence of digits and terminated by a decimal point.
The accompanying state-transition diagram illustrates how the automaton processes valid decimal constants:
graph LR q0 -- 0 --> q2((q2)) -- • --> q3 q0((q0)) -- δ --> q1((q1)) -- • --> q3((q3)) -- 0 ∪ δ --> q4(((q4))) q1 -- 0 ∪ δ --> q1 q4 -- 0 ∪ δ --> q4In this diagram, the transitions between states are denoted by directed edges, which show how the automaton moves from one state to another based on the current input character. For instance, the transition from
to represents a bundle of transitions for each digit in (1 through 9). For a concrete example, if the automaton processes the input string “0•2•”, it transitions through the following states: from
to upon reading ‘0’, then to upon reading ’•’, and finally to upon reading ‘2’. In the last state , the computation stops before the entire input has been consumed, as is an accepting state, confirming that the string “0•2•” is recognized as a valid decimal constant.
Deterministic Finite Automata (DFA)
Definition
A finite deterministic automaton (DFA), denoted as
, is a formal computational model that consists of five key components:
- State Set
: This is the finite, non-empty set of states that the automaton can occupy at any given time. - Input Alphabet
: This represents the finite set of input symbols, also known as the terminal alphabet, from which the automaton reads its input. - Transition Function
: The transition function defines how the automaton moves from one state to another based on the input symbol it reads. Formally, it is a mapping , meaning it takes a current state and an input symbol and returns the next state. - Initial State
: This is the state in which the automaton starts its computation. It is an element of . - Final States
: This is the subset of states that are considered accepting or final. If the automaton ends in one of these states after processing an input string, the string is considered accepted.
The meaning of the transition function
Property
A special case arises with the empty string
. For any state , we assume that no transition occurs when reading , meaning:
This expresses the idea that processing the empty string does not change the automaton’s state.
The domain of the transition function can be extended to handle not just single symbols but strings of symbols. The extended transition function
This definition means that to process the string
Theorem
A string
is recognized or accepted by the automaton if, starting from the initial state , the automaton can process the string and end in one of the final states. Formally, this condition is written as:
This means that there is a path from the initial state
to a final state, where the sequence of transitions corresponds to the symbols in the string . The empty string is recognized if, and only if, the initial state is also a final state, i.e., .
The language recognized or accepted by the automaton
In other words,
Error State and Total Automata
In a deterministic finite automaton (DFA), the error state (also called the sink or trap state) plays a key role. When the automaton enters this state, it gets “trapped” in it for all subsequent inputs, meaning that no valid transitions lead out of the error state. Additionally, the error state is not a final state, so no input string that leads to the error state will be accepted.
The transition function can be made total by introducing this error state, ensuring that for every combination of current state and input symbol, a transition is always defined.
Definition
The formal definition of the transition function with the error state is:
This ensures that any computation reaching the error state stays there indefinitely, preventing it from reaching any final state. Despite the addition of the error state, the total automaton still recognizes the same language as the original automaton, since it only affects inputs that would otherwise be rejected.
Clean Automata
Definition
In the context of finite automata:
- A state
is said to be reachable from a state if there is a sequence of transitions that leads from to . - A state is accessible if it can be reached from the initial state of the automaton.
- Similarly, a state is post-accessible if there is a path from that state to a final state.
- A state is considered useful if it is both accessible and post-accessible; otherwise, it is useless.
For every finite automaton, it is possible to construct an equivalent clean automaton by removing all useless states. This process simplifies the automaton without changing the language it accepts.
graph LR n1((not accessible<br>state)) -- a --> q0 n1 -- c --> q1 subgraph "clean automaton" direction LR q0((q0)) -- a --> q1((q1)) -- b --> q0 q1 -- a --> q3((q3)) end q0 -- b --> n2((not postaccessible<br>state)) q1 -- c --> n2
Minimal Automata
For every finite-state language, there exists a unique (up to renaming of states) minimal deterministic automaton that recognizes the language. This automaton has the fewest number of states necessary to accept the same language, making it an optimal representation. Although this minimization process is often not critical in compiler design, it is a standard way to represent collections of equivalent machines.
Some states in a given automaton may be redundant, meaning they can be combined without affecting the set of accepted or rejected strings. Such states are termed indistinguishable if they behave identically for all input strings. Specifically:
Definition
States
and are indistinguishable if and only if one of the following conditions holds:
is final and is not (or viceversa) is distinguishable from
Two states
- The error state
is distinguishable from every other state, because there is always a string for which (i.e., leads to a final state), while for every string (the error state never leads to a final state). - States
and are distinguishable if one is final and the other is not, because while . - Two states are distinguishable if, for some character
, the next states they transition to are themselves distinguishable.
Example: Equivalence classes of indistinguishable states
graph LR q0((q0)) q1((q1)) q2((q2)) q3((q3)) q0 -- a --> q1 q0 -- b --> q0 q1 -- a --> q1 q1 -- b --> q2 q2 -- a --> q3 q2 -- b --> q2 q3 -- a --> q3 q3 -- b --> q2For automaton
we construct a table of size , representing the indistinguishability relation; but, since the relation is symmetric, we do not have to fill the cases on and above the principal diagonal. mark with the case at position , when it discovers that the states and are distinguishable. We initialize with the cases such that one state only is final:
Then we examine every case
still unmarked and, for every character , we consider the next states and . If case already contains , meaning that is distinguishable from ; otherwise, if is not marked , the pair is written into case , as a future obligation. The cases not marked with identify the indistinguishable pairs, in our example only the pair . graph LR q0((q0)) q1((q1)) q2((q2, q3)) q0 -- a --> q1 q0 -- b --> q0 q1 -- a --> q1 q1 -- b --> q2 q2 -- a --> q2
To construct a minimal automaton
The formal transition in the minimal automaton can be represented as:
where
While minimizing states in an automaton is often advantageous for reasons of efficiency and simplicity, there are cases where state minimization may not be appropriate.
Example
For instance, in automata enriched with output functions, two states that are indistinguishable for recognizing a language may produce different outputs when performing certain computations. In such cases, it may be necessary to retain both states, despite their indistinguishability in terms of language recognition.
From Automata to Grammars
The process of constructing a right-linear grammar equivalent to a finite automaton involves translating the states and transitions of the automaton into grammatical rules. This conversion provides a formal way to represent the same language accepted by the automaton through a set of production rules in the grammar.
Algorithm
To create a right-linear grammar
from a given finite automaton, we follow these steps:
- Nonterminal Set: The set of nonterminals in the grammar corresponds to the states
of the automaton. Each state becomes a nonterminal. - Axiom: The initial state
of the automaton is designated as the axiom (starting symbol) of the grammar. - Production Rules:
- For every transition
in the automaton, there is a corresponding rule in the grammar: This rule indicates that from state , upon reading the terminal symbol , the automaton can transition to state . - If state
is a final state, it also includes the production rule: This indicates that the automaton can accept the empty string when in state .
A string
Example: From the automaton to the right-linear grammar
graph LR q0(((q0))) -- a --> q0 -- b --> q1((q1)) -- c --> q0 q1 -- a,b --> q2(((q2)))From the given automaton we can derive the right uni-linear grammar as follow
Sentence
is recognized in 3 steps by the automaton and it derives from the axiom in steps: Observe the grammar contains empty rules but of course it can be turned into the non-nullable normal form by means of the transformation.
For the example, first we find the set of nullable nonterminals
; then we construct the equivalent rules: Now
is eliminated because its only rule is empty. Finally, grammar cleaning produces the rules: Of course the empty rule
must stay there because is the axiom, which causes the empty string to be a sentence. In this normal form of the grammar it is evident that a move entering a final state
: may correspond to two rules
, one producing the nonterminal , the other of the terminal type.
Nondeterministic Automata
Nondeterministic automata are theoretical models in computer science used to recognize patterns and processes in formal languages. They are particularly relevant when analyzing right-linear grammars, which can exhibit nondeterministic behavior through alternative production rules.
Example
Consider a scenario where a right-linear grammar includes two alternative rules that begin with the same terminal character
. graph LR A((A)) -- a --> B((B)) A -- a --> C((C))For example, the grammar might be defined as follows:
In this context, the symbol
represents the set of terminal symbols, while denotes the set of non-terminal symbols. The presence of these alternative rules allows for multiple pathways or choices from a single state in the associated automaton.
When we translate these grammar rules into the framework of a nondeterministic finite automaton (NFA), we observe that two arrows labeled with the same terminal character
In addition to the nondeterministic transitions associated with terminal symbols, we also encounter what is known as a copy rule. For instance, consider the following production:
This rule indicates a transition from state
Motivation of Nondeterminism
Concision
Defining a language using a nondeterministic machine often leads to a more concise and readable representation. Nondeterministic automata allow multiple transitions from a single state or even spontaneous transitions (epsilon moves) without consuming input symbols. This flexibility reduces the need for complex state configurations, making the definition of the language simpler and more intuitive. By allowing choices in transitions, nondeterministic machines can efficiently describe languages with fewer states and transitions compared to deterministic models, contributing to a clearer and more streamlined formal definition.
Example: Penultimate Character
Consider a language where a string, such as
, is defined by having the character in the penultimate position. graph LR q0((q0)) -- a | b --> q0 q0 -- b --> q1((q1)) q1 -- a | b --> q2(((q2)))The regular expression for this language is:
Given an input string, the automaton seeks a computation path from the initial state to the final state, labeled with the input characters. If successful, the string is accepted. For example, the string “baba” is recognized with the following computation:
Other computations are possible but may fail to recognize the string if they do not reach the final state. For instance, the path:
fails because it does not reach the final state. The same language can be accepted by the deterministic automaton
: graph LR p0((p0)) -- a --> p0 -- b --> p1((p1)) -- b --> p3((p3)) -- b --> p3 p1 -- a --> p2((p2)) -- b --> p1 p2 -- a --> p0 p3 -- a --> p2
Left-Right Interchange and Language Reflection
Nondeterminism plays a significant role in the process of string reversal, particularly when converting a deterministic finite automaton (DFA) to recognize the reflection
To construct a new machine that recognizes
Algorithm
- First, we switch the initial state of the original DFA to become a final state in the new automaton, and vice versa. This change reflects the need to accept strings that, when read in reverse, reach the new starting point.
- Second, we reverse the direction of all arrows (transitions) in the automaton. This step means that if a transition in the original machine moves from state
to state on input , the new machine will have a transition from state to state on the same input .
Through these modifications, the resulting nondeterministic finite automaton (NFA) can accept any string that belongs to the reflected language
Example
The language having
as penultimate character is the reflection of the language having the second character equal to :
is recognized by the deterministic automaton graph TD subgraph 1[ ] direction RL q2((q2)) -- a | b --> q1((q1)) -- b --> q0(((q0))) -- a | b --> q0 end subgraph 2[ ] direction LR q0'((q0)) -- b --> q1'((q1)) -- a | b --> q2'(((q2))) q0' -- a | b --> q0' end
Nondeterministic Recognizers
A nondeterministic finite automaton (NFA) is a computational model used to recognize formal languages, which allows for multiple possible transitions from a given state for a specific input.
Definition
In its basic form, without spontaneous moves (such as epsilon transitions), an NFA
is formally defined by four key components:
- State Set
: This represents the finite set of states the automaton can be in. - Terminal Alphabet
: The alphabet defines the set of symbols or characters the automaton can read as input. - Initial States
: The subset of representing the starting states from which computations begin. - Final States
: The subset of representing the accepting states, where computations terminate successfully. - Transition Relation
: The transition function, which defines the possible moves the automaton can make. Unlike deterministic automata, the transition relation in an NFA allows for multiple possible next states for a given state and input symbol.
A computation in an NFA is a sequence of transitions between states such that each transition starts from where the previous one ended. Formally, a computation can be written as:
In this sequence,
For a string
- Starts at an initial state
, - Ends in a final state
, - Has the string
as its label, meaning the sequence of transitions matches the input string.
In particular, every state is the origin and termination of a computation of length
The language
In other words, the language consists of all strings
Example: Searching a word in a text
Given a word
, to recognize if a text contains that word, submit the text to the finite automaton that accepts the (regular) language . For instance, suppose to search the word
graph LR p((p)) -- b --> q((q)) -- b --> r((r)) p -- a | b --> p q -- a | b --> qThe string “abbb” labels several computations that start from the initial state
The first two computations do not find the word looked for. The last two find the word, respectively, at position
and
Transition Function
In a nondeterministic finite automaton (NFA), the moves can be interpreted as a finite function that computes sets of possible next states, rather than a single state. For an NFA defined as
Here,
-
For any terminal character
: The transition function outputs a set of states reachable from state upon reading the terminal symbol : This indicates that from state
, reading character can lead to multiple potential states . -
For the empty string
: The transition function indicates that the automaton can stay in the same state when reading the empty string. For any state : This means that
-transitions do not change the current state. -
For any terminal string
: The transition function can also determine the set of states reachable after reading a string composed of terminal symbols from . For any state and string : This definition reflects all states
that can be reached from state after processing the entire string .
The language accepted by the NFA
Theorem
Specifically, a string
is accepted if, after processing it, the current set of states contains at least one final state. Formally, this can be expressed as: In this formulation,
consists of all strings for which there exists an initial state from which the automaton can transition to a state in after reading the string .
Automata with Spontaneous Moves
Spontaneous moves, commonly referred to as epsilon moves (or
The ability to incorporate
For example, when building an automaton that recognizes a more complex pattern,
-arcs can be employed to connect various sub-automata without requiring the input of additional terminal symbols.
Uniqueness of the Initial State
While a nondeterministic automaton can have multiple initial states, it is straightforward to construct an equivalent NFA that contains only a single initial state. This can be achieved through the following steps:
Steps
- Add a New Initial State: Introduce a new state
to serve as the sole initial state of the automaton. - Connect to Existing Initial States: Use
-arcs to connect to each of the existing initial states of the original automaton. This effectively allows to transition to these states without consuming any input. - Modify the Original Initial States: Designate the original initial states as non-initial states.
This construction ensures that any computation within the new automaton will accept a string if and only if the original automaton accepts it. By connecting
While
Example: Compositional Definition of Decimal Constants
This language includes constants such as
. The part before the decimal point may be missing (e.g., ), but it cannot contain leading zeroes. Trailing zeroes are allowed at the end of the fractional part. The language is defined by the regular expression: The automaton reflects this structure. Spontaneous moves (epsilon moves) do not affect recognition: a string
is recognized if it labels a computation from an initial state to a final state. graph LR A((A)) -- ɛ, 0 --> C((C)) -- • --> D((D)) -- 0,...,9 --> E((E)) -- 0,...,9 --> E A -- 1,...,9 --> B((B)) -- 0,...,9 --> B -- ɛ --> CFor example, the string
is accepted with the computation: The number of steps in the computation can exceed the length of the input string due to epsilon moves. However, the time complexity remains linear, assuming no cycles of spontaneous moves.
The family of languages recognized by such nondeterministic automata is called finite-state.
Correspondence Between Automata and Grammars
There is a well-established relationship between formal grammars and automata, particularly when it comes to right-linear grammars and finite automata. To explore this connection, consider a strictly right-linear grammar
A derivation in a strictly right-linear grammar corresponds directly to a computation in a finite automaton, and vice versa. This correspondence arises because:
- In a right-linear grammar, each production rule is of the form
or , where and are non-terminal symbols from the set , and is a terminal symbol from the alphabet . This structure aligns with the transition function in an automaton, where reading a symbol from the input moves the automaton from one state to another. - A grammar derivation involves successively applying production rules to generate a string. Similarly, an automaton computation involves making transitions between states as symbols are read from the input string. Therefore, each step in the grammar’s derivation can be mapped to a corresponding state transition in the automaton.
This direct correspondence between the two models ensures that they define the same language. If a string can be derived using the grammar, the automaton can recognize it, and if the automaton accepts a string, it can be derived using the grammar.
| Right-Linear Grammar | Finite Automaton | |
|---|---|---|
| 1 | Nonterminal set | Set of states |
| 2 | Axiom | Initial state |
| 3 | Transition | |
| 4 | ||
| 5 | Final state |
The equivalence between grammars and automata can be summarized as follows:
A language is generated by a right-linear grammar if and only if it is recognized by a finite automaton.
This means that for every language generated by a right-linear grammar, there exists a corresponding finite automaton that can recognize the same language, and vice versa.
This also holds for left-linear grammars, though the structure of the grammar is reversed (with production rules of the form
In a right-linear grammar, if there are terminal rules of the form
- The automaton will have a final state
in addition to those states corresponding to non-terminal symbols of the grammar. - When the grammar includes a terminal rule such as
, the automaton will have a transition that moves to this final state upon reading the terminal symbol . - This move ensures that the automaton correctly handles the end of the string, transitioning to a final (accepting) state after reading the last terminal symbol in the input.
Example: Right-linear grammar and nondeterministic automaton
Right-linear grammar but not strictly
Going back to the example about the recognition of
, we drop the assumption of nonlinearity in the strict sense graph LR S((S)) -- a --> q((q)) -- a --> X((X)) -- b --> X -- b --> f((f))
The not strictly right-linear rule
is simply converted to a cascade of two arcs, with an intermediate state after the first . Moreover, the new final state has been added to mirror the last step of a derivation using rule .
Ambiguity of Automata
Definition
An automaton is ambiguous if a string
can be accepted through two or more distinct paths, meaning multiple computations lead to the same result.
This directly corresponds to ambiguity in the related grammar: an automaton is ambiguous if, and only if, the grammar generating the same language is also ambiguous. In other words, if a string has multiple derivations in the grammar, the automaton will have multiple accepting paths for that string.
Ambiguity complicates language recognition and can be resolved by simplifying the automaton, such as converting it into a deterministic form, which has a unique path for each input string. This ensures clarity and efficiency in practical applications.
Left-Linear Grammars and Automata
The REG family can also be characterized using left-linear grammars. By swapping left with right, the correspondence between such grammars and automata becomes evident.
Consider a grammar
Example: From left-linear grammar to automaton
Given grammar
: the reflected grammar
is The corresponding automaton
recognizing the mirror language and the recognizer for language are graph TD subgraph 1[ ] direction LR S((S)) -- a | b --> A((A)) -- b --> B(((B))) -- a | b --> B end subgraph 2[ ] direction RL B'((B)) -- a | b --> B' -- b --> A'((A)) -- a | b --> S'(((S))) endIncidentally, the language has a
in the position before the last.
From Automaton to Regular Expression Using the BMC Method
The BMC method, developed by Brzozowski and McCluskey, is also known as the “node elimination” method. It provides a way to convert a finite automaton directly into a regular expression by progressively eliminating internal states while preserving the automaton’s language. The key assumption in this method is that the initial state
The states other than
The essence of the BMC method lies in the systematic elimination of internal nodes. After each elimination, one or more compensation arcs are introduced to maintain the language recognized by the original automaton. These compensation arcs are labeled with regular expressions that capture the combined effect of the eliminated nodes. The process continues until only two nodes remain: the initial state
For each pair of states
The order in which the internal states are eliminated does not affect the final language recognized by the automaton. However, the complexity of the resulting regular expression may vary depending on the elimination order. Different orders can lead to different representations of the same language, with some regular expressions being more complex or simpler than others. Despite this, all regular expressions generated through different elimination sequences will be equivalent, meaning they describe the same set of strings.
Example: Automaton Normalization and Node Elimination in the Order
, graph BT subgraph "Automaton" direction LR p(((p))) -- a --> p -- b --> q((q)) -- b --> q -- a --> p end subgraph "Normalized Automaton" i((i)) -- ɛ --> p'((p)) -- a --> p' -- b --> q'((q)) -- b --> q' -- a --> p' -- ɛ --> t(((t))) endThe automaton is depicted both before and after normalization.
We illustrate the execution of the BMC algorithm by eliminating the states in the order
and . The elimination order does not affect the final result, although it may yield solutions of varying complexity, similar to solving simultaneous equations by elimination. For example, eliminating in the order
and would produce the regular expression .
Elimination of Nondeterminism
In order to enhance the efficiency of a finite automaton, it is often necessary to convert it into a deterministic form.
- A deterministic finite automaton (DFA) has no ambiguities in its transitions, meaning that from any given state and input, there is exactly one possible move.
- This contrasts with non-deterministic finite automata (NFA), where multiple transitions might be possible, leading to inefficiencies in terms of interpretation and execution.
However, every NFA can be transformed into an equivalent DFA, preserving the language it recognizes.
This transformation is crucial because every right-linear grammar (which can be represented by a finite automaton) has an equivalent deterministic version. Consequently, any ambiguous regular expression can be transformed into a non-ambiguous one, ensuring that every input string has a unique path of recognition.
Algorithm
The algorithm for converting a non-deterministic automaton into a deterministic one is typically divided into two distinct phases:
- Elimination of Spontaneous Moves (ε-Arcs) The first step in the process is to eliminate spontaneous moves. To remove these moves, an algorithm similar to the one used to eliminate copy rules in context-free grammars can be applied. This approach ensures that all transitions in the resulting automaton consume an input symbol, making it simpler to analyze and transform.
One practical method to execute this phase involves directly modifying the state-transition graph by cutting off ε-arcs. This means identifying all ε-transitions and replacing them by combining their effects into the existing transitions that consume input symbols. By working on the graph in this way, it becomes possible to remove the non-determinism introduced by ε-moves while maintaining the structure of the automaton.
- Subset Construction for Deterministic Transitions The second phase involves handling the non-determinism caused by multiple transitions from the same state on the same input symbol. In an NFA, it is possible for one state to have several outgoing transitions labeled with the same input symbol, each leading to different states. To resolve this ambiguity, the subset construction algorithm is used, also known as the “powerset construction.”
This method transforms the state set of the non-deterministic automaton into a new set of states for the deterministic automaton. Instead of representing individual states, each state in the new DFA represents a set of states from the original NFA. Whenever the NFA encounters non-deterministic choices, the DFA aggregates the possible resulting states into one “superstate.” Thus, the DFA effectively simulates all possible transitions of the NFA simultaneously, but in a deterministic manner.
By constructing the state set in this way, the DFA avoids any ambiguity in its transitions, as it uniquely identifies the next state for every input symbol from any current state.
While the subset construction method guarantees the transformation of any NFA into an equivalent DFA, it can lead to an exponential increase in the number of states in the worst case. However, the trade-off is that the resulting DFA will have deterministic transitions, making it much faster and more predictable in its execution.
The elimination of spontaneous moves and the subsequent replacement of non-deterministic transitions is essential for optimizing the automaton’s performance. By ensuring that the automaton is in deterministic form, the language it recognizes can be processed efficiently, whether in lexical analysis, pattern matching, or other applications of formal language theory.
Example: Eliminating ε-Arcs by Removing Copy Rules from the Grammar
Consider the automaton with ε-arcs:
graph LR S((S)) -- ɛ --> A((A)) -- a --> B((B)) A -- e --> D((D)) -- c --> C((C)) -- b --> D -- d --> A D -- ɛ --> S C -- a --> SThe original left-linear grammar is:
After step 1, in the middle of the process, and after steps 2, 3, and the part of step 4 that deletes ε-arcs, the automaton is transformed as follows. Since state B becomes inaccessible, it is deleted:
graph LR S((S)) -- e --> D((D)) A((A)) -- e --> D((D)) -- e --> D -- c --> C((C)) -- b --> D -- d --> A C -- a --> S B((B))An alternative way to solve the problem involves transforming the automaton into a right-linear grammar, from which the copy rules are then eliminated:
From Regular Expression to Recognizer
There are several algorithms to transform a regular expression into an automaton, each differing in characteristics such as determinism, automaton size, and construction complexity. Below are two notable methods:
-
Thompson’s Construction (Structural Method):
- Decomposes the regular expression into subexpressions until reaching the atomic constituents, i.e., the terminal symbols.
- Constructs recognizers for the subexpressions, connects them, and builds a network of recognizers that implement the union, concatenation, and star operators.
-
Berry-Sethi Method (BS): Constructs a deterministic recognizer without spontaneous moves, often resulting in a larger automaton compared to Thompson’s method.
Thompson Structural Method
The Thompson Structural Method is a key approach for constructing a finite automaton from a regular expression (regex). This method decomposes a regular expression into its fundamental components and builds an automaton by progressively connecting these components. The automaton constructed by this method is a non-deterministic finite automaton (NFA), often containing many nondeterministic branches and
Despite the nondeterminism, Thompson’s method is powerful because it aligns directly with the closure properties of regular languages, supporting operations like concatenation, union, and Kleene star.
Algorithm
Decompose the Regular Expression: Start by breaking the regular expression into smaller, atomic parts. These parts correspond to basic operations like individual symbols, union, concatenation, and the Kleene star.
Construct Component Automata: For each atomic part, construct a small automaton fragment. Each fragment consists of an initial state (without incoming arcs) and a final state (without outgoing arcs). If these conditions aren’t met, new states are introduced, similar to the BMC algorithm.
Combine the Components: These atomic automata are then combined using ε-transitions to reflect the structure of the regular expression. Thompson’s method ensures that each basic operator in the regular expression is mapped to its corresponding structure in the automaton.
Union: For the union operator
, two branches are created. One path recognizes , and the other path recognizes , with -transitions connecting these paths to a shared start and end point. Concatenation: For concatenation, the final state of the first subautomaton is connected via an
-transition to the initial state of the second subautomaton. Kleene Star: The Kleene star (
) is handled by introducing loops with -transitions that allow the automaton to repeat certain paths indefinitely or skip them entirely.
Thompson’s method effectively transforms the regular expression into a visual and functional representation as an NFA. The use of
Example: from regular expression to automaton using Thompson's method
Decompose the regular expression
into subexpression, identified by the names Then, apply the mapping to each subexpression, thus producing the automaton.
graph LR 1(( )) -- ɛ --> 2(( )) -- a --> 3(( )) -- ɛ --> 4(( )) -- ɛ --> 7(( )) -- ɛ --> 8(( )) -- b --> 9(( )) -- ɛ --> 10(( )) 1 -- ɛ --> 5(( )) -- ɛ --> 6(( )) -- ɛ --> 4 7 -- ɛ --> 10 9 -- ɛ --> 8Notice that we have moderately simplified the construction, to avoid a proliferation of states. Of course, several states are redundant and could be coalesced.
Local Sets of a Language
In automata theory and formal languages, local sets play a crucial role in understanding and constructing automata that are equivalent to a given regular expression or language
Definition
Given a language
defined over the alphabet , three important local sets are identified:
Initials Set
: This set contains the alphabet symbols that can appear as the first character of a string in the language . In other words,
consists of all symbols from for which there exists some string in that starts with . It provides a direct correspondence between the initial states of the automaton and the possible first characters of valid strings. Finals Set
: This set contains the symbols from that can appear as the last character of a string in the language . Similar to the initials set, the finals set captures the ending behavior of the strings in
, mapping to the possible final states in an automaton that recognizes . Diagrams Set
: This set consists of all pairs of consecutive symbols (bigrams) that can occur in the strings of . The elements of
are pairs of symbols , where the combination of followed by occurs somewhere in the strings of the language . This set helps describe the valid transitions between consecutive states in the automaton that correspond to valid symbol pairs in the strings. The complementary diagrams
represent the set of symbol pairs that do not appear as consecutive symbols in the strings of . Formally, it is defined as: This set captures the pairs of symbols that are forbidden or impossible in the language
, and it helps define the structure of the automaton by indicating where transitions should not exist.
These local sets are used in constructing automata that are equivalent to a given regular expression. Each state in the automaton can be mapped to these local sets, reflecting the behavior of the regular expression at various points. For instance:
- Initial states are directly related to the set
, where the automaton begins its recognition process. - Final states correspond to the set
, where the automaton successfully accepts a string. - Transitions between states are informed by
, ensuring that the automaton only transitions between symbols that appear consecutively in valid strings.
By leveraging the local sets, automata can be constructed efficiently and in direct correspondence with the structure of the regular expression, ensuring that the language recognized by the automaton matches the language defined by the regular expression.
To analyze a regular expression (regex)
The first step is to determine if the regex
- If
, then - If
, then
Example: Nullability Calculation
Consider the regex
: This computation shows that
does not generate the empty string.
The following table summarizes the rules for computing the nullability predicate and the local sets of initials, finals, and digrams for different types of regular expressions:
| Expression | Nullability Predicate | Set of Initials | Set of Finals | Set of Digrams |
|---|---|---|---|---|
Berry-Sethi Algorithm
The Berry-Sethi Algorithm is an efficient method for converting a regular expression into an equivalent finite automaton (FA). It provides a structured approach to handle regular expressions with multiple states and nondeterminism, and it can also accommodate ε-moves (epsilon transitions). Below is a detailed breakdown of the algorithm and its components.
-
Numbering the Generators: To distinguish the different generators (symbols) in the regular expression, each generator is assigned a unique index. This transformation is applied to the regex, which results in a numbered version of the expression. For example, the regex
becomes . -
End-Marked Regular Expression: The expression
is treated as an end-marked regular expression , which includes an end marker (denoted as ). This allows the algorithm to consider the termination of the input string. -
Followers of a Generator: The followers of a generator
are defined as: : This gives the set of all symbols that can follow the generator in the context of the expression. : The end marker has no followers.
-
State Marking: States in the automaton are tagged with subsets of
. When a state is examined, it is marked as visited to prevent repeated processing. -
Final States: The final states in the automaton are those that include the end-of-text marker.
Algorithm Steps
The algorithm uses the following steps to create a finite automaton
for the unnumbered regex :
Initialization:
- Set the initial state:
- Initialize the state set:
- Initialize the transition function:
Processing States:
Example
Apply the algorithm to the r.e.
. For the numbered r.e. , the sets of initials and followers are:
We mention that the automaton thus produced may contain (moderately) more states than are necessary, but of course it can be minimized by the usual method
Regular Expressions with Complement, Intersection, and Set Difference
Regular expressions (regexps) can be enhanced with operators such as complement, intersection, and set difference, which allow for more concise and powerful representations of languages. These operators expand the expressive power of regular expressions, making them more versatile in defining complex language constraints.
Closure Properties of Regular Languages
A key property of regular languages is that they are closed under complement, intersection, and set difference. This means that
if
and are regular languages, their complement , their intersection , and the set difference are also regular languages. Mathematically, we can express this closure as follows:
This guarantees that applying these operations does not take us out of the realm of regular languages, which is essential when designing automata for recognizing specific patterns.
Given a regular language
Algorithm
To construct a DFA that recognizes
, follow this algorithm:
- Complete the Automaton: Create an error state
(not originally in the set of states ) and ensure that for every undefined transition, the automaton moves to this error state. - Swap Final and Non-final States: The set of final states for the complement automaton becomes
, where represents the original final states. - Define Transition Function: The transition function for the complement automaton is adjusted as follows:
- For a state
and input symbol , if , the transition remains unchanged. - If
is undefined, the automaton moves to the error state . - Once in the error state, the automaton stays in
for any input.
This modified automaton recognizes all strings that the original DFA does not accept, effectively implementing the complement operation.
Intersection of Regular Languages
Property
The intersection of two regular languages is also a regular language.
One method to construct the DFA for the intersection is to use De Morgan’s law, which reduces intersection to complement and union:
Alternatively, a more direct approach involves constructing the Cartesian product of the two automata, which simulates both automata in parallel, checking whether a string is accepted by both simultaneously.
Set Difference of Regular Languages
The set difference between two regular languages
This formula indicates that the set difference is the intersection of the first language with the complement of the second language, ensuring that only the strings in
Caution with Non-Deterministic Automata
The construction of the complement automaton requires that the original automaton be deterministic. If the automaton is non-deterministic, the resulting complement may not be correct, as it might violate the condition that
. This happens because a non-deterministic automaton could accept strings that should belong to both the original and complement languages, contradicting the definition of a complement. Therefore, it is crucial to convert a non-deterministic automaton to its deterministic equivalent before constructing its complement.
Cartesian Product of Automata
The Cartesian product of automata enables the construction of a single automaton that simulates the behavior of two automata working in parallel on the same input string. This is particularly useful for creating an automaton that recognizes the intersection of two regular languages, a common task in computational theory.
One approach to obtaining the intersection automaton is by applying De Morgan’s theorem, which allows reducing the problem of intersection to operations involving complement and union.
Algorithm
The steps are as follows:
- Construct deterministic recognizers for the two regular languages.
- Build the complement automata for each of the two languages by applying the complement construction (as described in the theory of regular expressions).
- Construct the union automaton of the two complement automata, which can be done using methods such as the Thompson construction.
- Determinize the union automaton by applying the subset construction (also known as powerset or BS algorithm) if the union automaton is non-deterministic.
- Complement the resulting automaton to obtain the automaton recognizing the intersection of the original two languages.
While this method is systematic and relies on known automata construction techniques, there is a more direct method to construct the intersection automaton through the Cartesian product of automata.
The intersection of two languages can be recognized directly by constructing the Cartesian product of the state sets of their respective automata. Even though the resulting automaton may be non-deterministic, this method offers a more straightforward approach. Here is how it works:
- Assume that both automata have no spontaneous or epsilon (
) transitions, although they may still be non-deterministic. - The state set of the product automaton consists of pairs of states, one from each of the original automata. If
is a state of the first automaton and is a state of the second, a state in the product automaton is represented as . - A transition between states occurs when both automata, upon reading the same input symbol, transition to new states. Specifically, if the first automaton moves from
to and the second automaton moves from to upon reading the symbol , then the product automaton transitions from to .
Mathematically, the move is defined as:
The product automaton has a valid move only if both original automata can transition on the same input symbol. The initial state of the product automaton is the pair of initial states from the original automata, and the final states are the Cartesian product of the final states of the two automata.
The Cartesian product construction effectively simulates both automata in parallel. If a string is accepted by the product automaton, it means that both original automata accepted the string. Conversely, if either automaton (or both) rejects the string, the product automaton also rejects it. This behavior directly aligns with the notion of intersection: a string belongs to the intersection of two languages if and only if both languages accept the string.
NOTE
Useless States and Minimization: The product automaton may contain states that do not contribute to recognizing the intersection language. These are known as useless states and should ideally be removed through a minimization process to simplify the automaton.
Determinism: If either of the original automata is deterministic, the product automaton will also be deterministic. However, if both automata are non-deterministic, the product automaton will generally be non-deterministic as well.
Example: Intersection Automaton
Consider two regular languages:
, which represents strings over the alphabet that contain the substring “ab”. , representing strings that contain the substring “ba”. To construct the intersection automaton, we take the Cartesian product of the state sets of the two automata recognizing
and . The product automaton will be non-deterministic and may include states that are not useful for recognizing the intersection language, such as states that cannot lead to acceptance. Minimizing the resulting automaton can further optimize it by removing these unnecessary states.
The Cartesian product construction can be modified to handle other language operations, though some, like union and shuffle, may be more complex to implement.
- The union of two languages can be done by merging the state sets and transitions of the automata, though ensuring determinism often requires further steps such as subset construction.
- Shuffle is a less common operation that interleaves two strings, and constructing an automaton for shuffle can be quite challenging.