Practical – 7
Aim : Write a program to minimize any given DFA.
Introduction:
Deterministic Finite Automata (DFA) are widely used in lexical analyzers, parsers, and various
computational models. However, a DFA generated from an NFA or designed manually may not be
optimized—it could have unnecessary or redundant states. DFA minimization is a technique used to
produce the smallest possible DFA that accepts the same language as the original. Minimizing a DFA
leads to improvements in performance, memory usage, and efficiency, which are critical for real-world
applications like compilers and protocol analysis.
Functional Requirements:
• Read a DFA transition table from user input.
• Identify and remove inaccessible (unreachable) states.
• Partition the DFA states into groups of equivalent and non-equivalent states.
• Merge equivalent states to form the minimized DFA.
• Construct and display the minimized DFA transition table systematically.
• Clearly indicate the initial and final states in the minimized DFA.
• Handle dead states (trap states) appropriately.
Implementation Approach:
The DFA minimization will be implemented in the C language.
The program will first remove any unreachable states to simplify the DFA.
Then it will use the partition refinement method (also known as the table-filling method or
equivalence partitioning) to distinguish between distinguishable and indistinguishable states.
Equivalent states will be merged to form new single states.
The minimized DFA transition table will be displayed clearly, showing the new states and transitions..
Code
#include <stdio.h>
#include <stdbool.h>
#define MAX 20
int dfa[MAX][MAX];
bool final[MAX];
bool distinguishable[MAX][MAX];
int n_states, n_symbols;
char symbols[MAX];
// Function to print minimized DFA
void printMinimizedDFA(int group[]) {
printf("\nMinimized DFA States and Transitions:\n");
printf("State\t");
for (int i = 0; i < n_symbols; i++) {
printf("%c\t", symbols[i]);
}
printf("\n-------------------------------------------------\n");
bool printed[MAX] = {false};
for (int i = 0; i < n_states; i++) {
if (!printed[group[i]]) {
printed[group[i]] = true;
printf("Q%d\t", group[i]);
for (int j = 0; j < n_symbols; j++) {
printf("Q%d\t", group[dfa[i][j]]);
}
printf("\n");
}
}
}
int main() {
int i, j, k;
printf("Enter number of states: ");
scanf("%d", &n_states);
printf("Enter number of input symbols: ");
scanf("%d", &n_symbols);
printf("Enter the input symbols (no spaces): ");
for (i = 0; i < n_symbols; i++) {
scanf(" %c", &symbols[i]);
}
printf("Enter DFA transition table (next state for each input symbol):\n");
for (i = 0; i < n_states; i++) {
for (j = 0; j < n_symbols; j++) {
printf("From state %d on symbol %c: ", i, symbols[j]);
scanf("%d", &dfa[i][j]);
}
}
printf("Enter final states (1 for final, 0 for non-final):\n");
for (i = 0; i < n_states; i++) {
printf("Is state %d a final state? ", i);
scanf("%d", (int *)&final[i]);
}
// Step 1: Mark distinguishable states (final vs non-final)
for (i = 0; i < n_states; i++) {
for (j = 0; j < n_states; j++) {
distinguishable[i][j] = (final[i] != final[j]);
}
}
// Step 2: Iteratively mark distinguishable pairs
bool updated;
do {
updated = false;
for (i = 0; i < n_states; i++) {
for (j = i+1; j < n_states; j++) {
if (!distinguishable[i][j]) {
for (k = 0; k < n_symbols; k++) {
int a = dfa[i][k];
int b = dfa[j][k];
if (a > b) { int temp = a; a = b; b = temp; } // Ensure a < b
if (distinguishable[a][b]) {
distinguishable[i][j] = true;
updated = true;
break;
}
}
}
}
}
} while (updated);
// Step 3: Create groups (equivalent states)
int group[MAX];
int g = 0;
for (i = 0; i < n_states; i++) {
if (group[i] == 0) {
g++;
group[i] = g;
for (j = i+1; j < n_states; j++) {
if (!distinguishable[i][j]) {
group[j] = g;
}
}
}
}
printMinimizedDFA(group);
return 0;
}
Input
Output