DFA to Regular Expression Conversion using State Elimination Method

-

 

Download pdf

DFA to Regular Expression

What is Deterministic Finite Automata?

Deterministic finite automata (or DFA) are finite state machines that accept or reject strings of characters by parsing them through a sequence that is uniquely determined by each string. The term “deterministic” refers to the fact that each string, and thus each state sequence, is unique. These machines are called finite because there are a limited number of possible states which can be reached. In practice, DFAs are made up of five components (and they’re often denoted by a five-symbol set known as a 5-tuple). These components include:

  • A finite number of states
  • A set of symbols known as the alphabet, also finite in number
  • A function that operates the transition between states for each symbol
  • An initial start state where the first input is given or processed
  • A final state or states, known as accepting states.


 

What is Regular Expresion?

The language accepted by finite automata can be easily described by simple expressions called Regular Expressions. It is the most effective way to represent any language. The languages accepted by some regular expression are referred to as Regular languages.



DFA to Regular Expression


The two popular methods for converting a given DFA to its regular expression are

 



State Elimination Method

The State elimination method follows the following general set of rules:

1.   Add a new initial state (I). Make a null transition from the old initial state to the new      initial state.

2.   Add a new final state (F). Make null transition(s) to the new final state.

3.   Eliminate all states, except I and F, in the given finite automaton. Perform the elimination of states by checking the in-degrees and out-degrees of states and taking a cross product.

After steps 1 and 2, the (I) state will not have any inward transitions, and the state (F) state will not have any outward transitions.

Example

Let's consider the following finite automaton:



Step 1: Add an initial state

Add a new initial state, I. Make a null transition from state I to state q0​.



Step 2: Add a final state

Add a new final state, F. Make a null transition from state 3q3​ to state F.



Step 3: State elimination

Perform the elimination of states other than I and F.

Step 3.1

Eliminate state q0​.



Eliminating q0


Step 3.2

Eliminate state q3​. Concatenate transitions from state q3​ to state F as per the basic rules of writing regular expressions.



Eliminating q3

Step 3.3

Eliminate q1​. Check for the in-degree and out-degree of state q1​. Write the regular expressions for the new transitions acquired after removing state q1​.



Eliminating q1

Step 3.4

Eliminate state q2

​.


Eliminating q2

Step 3.5

Put it all together.



The final regular expression

Result

The resultant regular expression for the given finite automaton is as follows:

Download pdf



Comments

Post a Comment

Popular posts from this blog

What is the Difference between Scanning and Parsing

-
Image
  What is the Difference between Scanning and Parsing The main difference between scanning and parsing is that scanning is the process of reading the source code one character at a time in a methodical manner to convert them into tokens while parsing is the process of taking the tokens and generating a parse tree as the output. Generally, a compiler is a software program that is capable of converting the source code into machine code so that the computer can execute that machine code. The compiler goes through multiple phases to compile a program. Scanning and parsing are two activities that occur during this compilation process. Overall, scanning occurs at the lexical analysis phase, whereas parsing occurs at the syntax analysis phase. Furthermore, the lexical analyzer performs scanning while the parser performs parsing.
Read more

Syntax Tree

-
Image
Download pdf What is Syntax Tree? Tree in which each leaf node describes an operand & each interior node an operator. The syntax tree is shortened form of the Parse Tree. Example1  − Draw Syntax Tree for the string a + b ∗ c − d. Rules for constructing a syntax tree Each node in a syntax tree can be executed as data with multiple fields. In the node for an operator, one field recognizes the operator and the remaining field includes a pointer to the nodes for the operands. The operator is known as the label of the node. The following functions are used to create the nodes of the syntax tree for the expressions with binary operators. Each function returns a pointer to the recently generated node. ·         mknode (op, left, right)  − It generates an operator node with label op and two field including pointers to left and right. ·         mkleaf (id, entry)  − It generates an identifier node with label id and the field including the entry, a pointer to the symbol tabl
Read more