A finite state automaton FSA in general is designed to recog

A finite state automaton FSA, in general, is designed to recognize words of a predetermined language. However, in some application, it is also desirable to have a FSA that can recognize words it rejects before. For instance, consider the symbol table manager of a compiler: it initially recognizes only a set of reserved words, but during the compilation of a program, it recognizes also identifiers it has seen before. Such a FSA need the ability to modify its language dynamically, and hence be referred to a dynamic finite state automaton. Your job for this assignment is to implement the dynamic finite state automaton that recognizes none initially, but some after reading files Inputl and Input2 described as follows. Both files are now posted on Bb. Input 1.txt: Reserved words of Java abstract boolean break byte case catch char class continue default do double else enum extends final finally float for if implements import instanceof int interface long native new package private protected public return short static super switch synchronized this throw throws transient try void volatile while Input2.txt: A Java program During this process, your dynamic FSA should extract identifiers and expand its vocabulary whenever a new identifier is read. An identifier must begin with a letter, an underscore O, or a dollar sign (S) followed by any combination of letters, digits, underscores, and dollar signs. Both cases of letter can be used, and Java is case-sensitive. You should use three special markers for different types of vocabulary: for the reserved words, for the new identifiers, and (a for the identifiers not shown at the first time. Your program should ignore punctuations and numbers, and process identifiers only

Solution

#include<stdio.h>

#include<string.h>

#define NO_OF_CHARS 256

int getNextState(char *pat, int M, int state, int x)

{

// If the character c is same as next character in pattern,

// then simply increment state

if (state < M && x == pat[state])

return state+1;

int ns, i; // ns stores the result which is next state

// ns finally contains the longest prefix which is also suffix

// in \"pat[0..state-1]c\"

// Start from the largest possible value and stop when you find

// a prefix which is also suffix

for (ns = state; ns > 0; ns--)

{

if(pat[ns-1] == x)

{

for(i = 0; i < ns-1; i++)

{

if (pat[i] != pat[state-ns+1+i])

break;

}

if (i == ns-1)

return ns;

}

}

return 0;

}

/* This function builds the TF table which represents Finite Automata for a

given pattern */

void computeTF(char *pat, int M, int TF[][NO_OF_CHARS])

{

int state, x;

for (state = 0; state <= M; ++state)

for (x = 0; x < NO_OF_CHARS; ++x)

TF[state][x] = getNextState(pat, M, state, x);

}

/* Prints all occurrences of pat in txt */

void search(char *pat, char *txt)

{

int M = strlen(pat);

int N = strlen(txt);

int TF[M+1][NO_OF_CHARS];

computeTF(pat, M, TF);

// Process txt over FA.

int i, state=0;

for (i = 0; i < N; i++)

{

state = TF[state][txt[i]];

if (state == M)

{

printf (\"\ Pattern found at index %d\", i-M+1);

}

}

}

// Driver program to test above function

int main()

{

char *txt = \"AABAACAADAABAAABAA\";

char *pat = \"AABA\";

search(pat, txt);

return 0;

}