- \n
- What are Finite Automata?<\/a><\/li>\n
- Types of Finite Automata<\/a>\n
- \n
- Deterministic Finite Automata<\/a><\/li>\n
- Non-Deterministic Finite Automata<\/a><\/li>\n<\/ul>\n<\/li>\n
- Finite Automata to Regular Expression<\/a>\n
- \n
- Example<\/a><\/li>\n<\/ul>\n<\/li>\n
- Regular Expression to Finite Expression<\/a>\n
- \n
- Example<\/a><\/li>\n<\/ul>\n<\/li>\n
- Block Diagram\u00a0<\/a><\/li>\n
- Minimization\u00a0<\/a>\n
- \n
- Example<\/a><\/li>\n<\/ul>\n<\/li>\n
- Limitations<\/a><\/li>\n
- Applications<\/a><\/li>\n<\/ol>\n
<\/a><\/p>\n
What are Finite Automata in Compiler Design?<\/h3>\n
Finite automata is a finite state machine that acts as a recognizer for a language. When it is provided with an input string it accepts or rejects the string based on whether the string is from the language or not.<\/p>\n
FA recognize the regular expression that is a set of strings and accepts it if it represents a regular language else it rejects it. When finite automata accept the regular expression, it compiles it to form a transition diagram.<\/p>\n
In finite automata, there is a finite state for each input. FAcan be categorized in two ways deterministic finite automata and non-deterministic finite automata.
\n<\/a><\/p>\nTypes of FA<\/h3>\n
There are two kind of FA:<\/p>\n
- \n
- Deterministic Finite Automata (DFA)<\/li>\n
- Non-Deterministic Finite Automata (NFA)<\/li>\n<\/ol>\n
<\/a><\/p>\n
Deterministic FA<\/h3>\n
In deterministic finite automata in response to a single input alphabet, the state transits to only one state. In DFA, no null moves are accepted.<\/p>\n
The DFA have five tuples as discussed below:<\/p>\n
\n{Q, \u03a3, q0<\/sub>, F, \u03b4}<\/p>\n
- \n
- Q = set of all states<\/li>\n
- \u03a3 = Set of all input alphabets<\/li>\n
- q0 <\/sub>= initial state<\/li>\n
- F = Set of Final State<\/li>\n
- \u03b4 = Transition function<\/li>\n<\/ul>\n<\/div>\n
The DFA can be represented by the transition graph. In the transition graph, the nodes of the graph represent the states and the edges represent the transition of one state to another. Let us take an example of DFA:<\/p>\n
![\"Deterministic](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Deterministic-Finite-Automata.jpg\")
<\/p>\nIn the above example of DFA, you can notice that with a single input \u2018a\u2019 state \u20180\u2019 transit t only one state \u20181\u2019. The transition table for the above DFA is as below:<\/p>\n
![\"Transition](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Transition-Table-of-DFA.jpg\")
\n<\/a><\/p>\nNon-Deterministic FA<\/h3>\n
In non-deterministic finite automata, in response to a single input alphabet, a state may transit to more than one state. The NFA also accept the NULL move.<\/p>\n
![\"Non-Deterministic](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Non-Deterministic-Finite-Automata.jpg\")
<\/p>\nIn the above example of NFA, you can notice that the state \u20180\u2019 with the input symbol \u2018a\u2019 can either transit to itself or to state \u20181\u2019.\u00a0 Now let us create a transition table for the NFA above.<\/p>\n
![\"Transition](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Transition-Table-of-NFA.jpg\")
<\/p>\nWith the transition table, it becomes easy to identify the transition on a given state with the given input. Although it takes a lot of space if there are a lot of input alphabets as most of the state do not perform any transition on most of the input symbols.<\/p>\n
Before we learn to convert a regular expression to FA or vice versa let us discuss in detail regular expression.<\/p>\n
What is Regular Expression?<\/h4>\n
A regular expression is a string that represents a regular language. An expression is said to be regular if the string is represented as:<\/p>\n
- \n
- a*<\/sup><\/strong>-> it means zero or more occurrence of a
\n{\u2208, a, aa, aaa, aaaa\u2026} \/\/ here * is a Kleene closure<\/li>\n- a+<\/sup><\/strong>-> it means one or more occurrences of a
\n{ a, aa, aaa, aaaa\u2026} \/\/ here + is a positive closure<\/li>\n- a.b<\/strong> -> it means the concatenation i.e. a will be followed by b<\/li>\n
- a|b<\/strong> -> it means the union i.e. either \u2018a\u2019 will appear or \u2018b\u2019<\/li>\n<\/ol>\n
So, this is the way in which the regular expression can represent a regular language. Like we follow the precedence of operators in mathematic like BODMAS. Here also we have precedence of operators in sequence:<\/p>\n
- \n
- Kleene Closure {a*<\/sup>}<\/li>\n
- Positive Closure {a+<\/sup>}<\/li>\n
- Concatenation {a.b}<\/li>\n
- Union {a|b}<\/li>\n<\/ul>\n
A regular expression is said to be valid we are able to derive the expression using primitive regular expressions using the finite application of rules that are a*<\/sup>, a+<\/sup>, a.b, a|b.<\/p>\n
Now, let us first learn to convert finite automata to the regular expression:
\n<\/a><\/p>\nFinite Automata to Regular Expression<\/h3>\n
There are two methods to convert finite automata to the regular expression:<\/p>\n
- \n
- Ardern\u2019s Method<\/li>\n
- State Elimination<\/li>\n<\/ol>\n
![\"Finite](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Finite-Automata-to-Regular-Expression.jpg\")
<\/p>\nFor explanation, we will be only discussing the state elimination method.<\/p>\n
State Elimination Method:<\/strong><\/p>\n
Here we will discuss the conversion of DFA to regular expression<\/p>\n
Step 1:<\/strong> The initial state of DFA should not have any incoming edge. If there is an incoming edge to the initial state you must create a new initial state.<\/p>\n
Step 2:<\/strong> There should not be any outgoing edges from the final state. If the final state has any outgoing edges then make a new final state.<\/p>\n
Step 3:<\/strong> There should be only one final state in any automata. If multiple final states exist, they all must be converted to a non-final state and we must create a new final state.<\/p>\n
Step 4:<\/strong> Eliminate all the intermediate states such that there will only be one initial state and one final state.
\n<\/a><\/p>\nExample<\/h3>\n
Let us take a finite automaton:<\/p>\n
![\"Finite](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Finite-Automata-to-Regular-Expression-1.jpg\")
<\/p>\nStep 1: <\/strong>As the initial state has an incoming edge we have to create a new initial state.<\/p>\n
![\"Finite](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Finite-Automata-to-Regular-Expression-2.jpg\")
<\/p>\nStep 2: <\/strong>As the final state has an outgoing edge then we have to create a new final state.<\/p>\n
![\"Finite](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Finite-Automata-to-Regular-Expression-3.jpg\")
<\/p>\nStep 3:<\/strong> Now you have to start eliminating the intermediate states so we have initially eliminated state \u20180\u2019.<\/p>\n
![\"Finite](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Finite-Automata-to-Regular-Expression-4.jpg\")
<\/p>\nStep 4:<\/strong> Next, we will eliminate the state \u20181\u2019.<\/p>\n
![\"Finite](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Finite-Automata-to-Regular-Expression-5.jpg\")
\n<\/a><\/p>\nRegular Expression to Finite Automata<\/h3>\n
Now let us take a regular expression (a+ba)*<\/sup>ba<\/strong> and we will learn to convert it to finite automata.<\/p>\n
<\/a><\/p>\n
Example<\/h3>\n
Step 1:<\/strong><\/p>\n
![\"Regular](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Regular-Expression-to-Finite-Automata-1.jpg\")
<\/p>\nStep 2:<\/strong><\/p>\n
![\"Regular](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Regular-Expression-to-Finite-Automata-2.jpg\")
<\/p>\nStep 3:<\/strong><\/p>\n
![\"Regular](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Regular-Expression-to-Finite-Automata-3-1.jpg\")
\n<\/a><\/p>\nBlock Diagram of FA<\/h3>\n
The concept of FA\u00a0 can be explained with the help of a block diagram as shown in the figure below:<\/p>\n
![\"Block](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/Block-Diagram-of-Finite-Automata.jpg\")
<\/p>\nLet us discuss the components of the block diagram of FA :<\/p>\n
- \n
- Input Tape:<\/strong> The input tape is divided into a number of blocks and has two ends left and right end. The left end is marked with \u20b5 and the right end of the input tape is marked with the $. Each block of the input tape has a single input symbol. The input tape is of infinite length.<\/li>\n
- Read Only Head:<\/strong> The input tape is indexed by a read-only head that point at only one block of input tape at a time. The head always starts reading from the leftmost block of the input tape and move towards the right.<\/li>\n
- Finite Control:<\/strong> The finite control block determines the state of finite automata ad also controls the movement of the head reading the input tape.<\/li>\n<\/ul>\n
<\/a><\/p>\n
Minimization of DFA<\/h3>\n
Minimization of DFA is reducing the DFA to minimum states and keeping it equivalent to the provided DFA. The FA must be containing some redundant states which unnecessarily increases the size of automata. Thus, it is essential to minimize the finite automata.<\/p>\n
The number of states in the FA decides the size of the automata. To reduce the size of the automat we must remove all the redundant states that do not affect the language accepted by the finite automata. Let us discuss the steps of minimizing the FA .<\/p>\n
- \n
- Remove all unreachable states.<\/li>\n
- Draw a transition table for all pairs of states.<\/li>\n
- Split the set of all states into two i.e., T1 (set of final states) T2 (set of non-final states).<\/li>\n
- Identify and merge equivalent state from set T1 and repeat the same for T2.<\/li>\n
- Now after merging the equivalent states in T1 and T2 combine the reduced sets T1 and T2.<\/li>\n<\/ol>\n
- Read Only Head:<\/strong> The input tape is indexed by a read-only head that point at only one block of input tape at a time. The head always starts reading from the leftmost block of the input tape and move towards the right.<\/li>\n
- Input Tape:<\/strong> The input tape is divided into a number of blocks and has two ends left and right end. The left end is marked with \u20b5 and the right end of the input tape is marked with the $. Each block of the input tape has a single input symbol. The input tape is of infinite length.<\/li>\n
- Positive Closure {a+<\/sup>}<\/li>\n
- a+<\/sup><\/strong>-> it means one or more occurrences of a
- Limitations<\/a><\/li>\n
- Block Diagram\u00a0<\/a><\/li>\n
- Regular Expression to Finite Expression<\/a>\n
- Non-Deterministic Finite Automata<\/a><\/li>\n<\/ul>\n<\/li>\n
- Types of Finite Automata<\/a>\n
![\"minimization](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/minimization-of-Finite-Automata1.jpg\")
<\/p>\n![\"minimization](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/minimization-of-Finite-Automata-2.jpg\")
<\/p>\n![\"minimization](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/minimization-of-Finite-Automata-2.1.jpg\")
<\/p>\n![\"minimization](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/minimization-of-Finite-Automata-2.2.jpg\")
<\/p>\n![\"minimization](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/minimization-of-Finite-Automata-3.jpg\")
<\/p>\n![\"minimization](\"https:\/\/binaryterms.com\/wp-content\/uploads\/2021\/12\/minimization-of-Finite-Automata-4.jpg\")