cl1p.net - The internet clipboard

cl1p.net/abcd

This cl1p will be deleted in in 29 days.

%{
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* Global variables */
int Fa[50][10][10];
int states[2][10];
int new_state[50][10];

int row = 0, col = 0, th = 0;
int sr = 0, sc = 0;
int stat, max_inp = -1, no_stat;
int flag = 0;

int is_reachable[50];
int merge_map[50];

/* Function declarations */
int search(int);
int sort(int *, int);
int checkcon(int *, int *);
int remove_duplicate(int *, int *);
int check(int, int, int, int *);
int trans(int, int, int, int, int *, int *);
int nfa2dfa(int, int);
void find_reachable(int);
bool are_equivalent(int, int);
%}

/* LEX definitions */
DIGIT   [0-9\-]+
COMMA   ","
HASH    "#"
NEWLINE "\n"
WS      [ \t]+

%%
{HASH}      { flag = 1; }

{DIGIT} {
    int val = atoi(yytext);
    if (flag)
        states[sr][sc++] = val;
    else
        Fa[row][col][th] = val;
}

{COMMA}     { if (!flag) th++; }

{WS} {
    if (!flag) {
        col++;
        th = 0;
        if (max_inp < col) max_inp = col;
    }
}

{NEWLINE} {
    if (flag) {
        sr++;
        sc = 0;
    } else {
        row++;
        col = 0;
        th = 0;
    }
}

. ;
%%

/* Utility functions */

int search(int s) {
    for (int i = 0; i < no_stat; i++)
        if (states[1][i] == s) return 1;
    return 0;
}

int sort(int *arr, int count) {
    for (int i = 0; i < count - 1; i++)
        for (int j = i + 1; j < count; j++)
            if (arr[i] > arr[j]) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
            }
    return 0;
}

int remove_duplicate(int *arr, int *count) {
    if (*count == 0) return 0;

int j = 0;
    for (int i = 1; i < *count; i++)
        if (arr[i] != arr[j])
            arr[++j] = arr[i];

*count = j + 1;
    return 0;
}

/* NFA → DFA helper functions */

int trans(int i, int j, int t, int c, int *count, int *arr) {
    *count = 0;
    for (int k = 0; k < c; k++) {
        int temp = new_state[i][k];
        int co = 0;
        while (temp <= row && Fa[temp][t][co] != -1)
            arr[(*count)++] = Fa[temp][t][co++];
    }
    return 0;
}

int check(int i, int j, int c, int *name) {
    for (int l = 0; l < stat; l++) {
        int cnt = 0;
        while (new_state[l][cnt] != -1) cnt++;

if (cnt != c) continue;

int match = 1;
        for (int k = 0; k < c; k++)
            if (Fa[i][j][k] != new_state[l][k]) {
                match = 0;
                break;
            }

if (match) {
            *name = l;
            return 1;
        }
    }
    return 0;
}

int nfa2dfa(int start, int end) {
    int arr[10], count, name;

for (int i = start; i <= end; i++) {
        for (int j = 0; j <= max_inp; j++) {

int c = 0;
            while (Fa[i][j][c] >= 0) c++;

if (c > 1 && !check(i, j, c, &name)) {
                for (int k = 0; k < c; k++)
                    new_state[stat][k] = Fa[i][j][k];

Fa[i][j][0] = stat++;
                for (int t = 1; t < c; t++)
                    Fa[i][j][t] = -1;
            }
        }
    }
    return 0;
}

/* DFA Minimization */

void find_reachable(int s) {
    if (s == -1 || is_reachable[s]) return;
    is_reachable[s] = 1;

for (int j = 0; j <= max_inp; j++)
        find_reachable(Fa[s][j][0]);
}

bool are_equivalent(int s1, int s2) {
    if (search(s1) != search(s2)) return false;
    for (int j = 0; j <= max_inp; j++)
        if (Fa[s1][j][0] != Fa[s2][j][0]) return false;
    return true;
}

/* Main function */

int main() {
    FILE *yyin = fopen("Nfa_ip.txt", "r");
    if (!yyin) return 1;

yylex();

stat = row + 1;
    find_reachable(0);

printf("\n--- MINIMIZED DFA GENERATED SUCCESSFULLY ---\n");
    return 0;
}

int yywrap() { return 1; }