Consider the following declaration:
typedef struct {
    int V;
    int E;
    char **Adj;
} automata;

An $$\texttt{automata}$$ is a directed weighted graph where weights are characters.

1. Write a function that reads and returns an $$\texttt{automata}$$.
2. Given a $$\texttt{starting vertex}$$, $$\texttt{ending vertex}$$ and a $$\texttt{string}$$, write the function
   $$\texttt{int recognize(automata* A, int start, int end, char* string)}$$
   that checks if the $$\texttt{string}$$ starts with the $$\texttt{starting vertex}$$ and ends with the $$\texttt{ending vertex}$$ and there is a path in between that is equal to the $$\texttt{string}$$. 
   Hint: Use DFS.

Example: in the following automata

$$\texttt{recognize(A, 0, 3, "aabbbbbbc")}$$ returns 1.
$$\texttt{recognize(A, 0, 3, "ac")}$$ returns 1.
$$\texttt{recognize(A, 0, 3, "abc")}$$ returns 1.
$$\texttt{recognize(A, 0, 3, "ab")}$$ returns 0.
$$\texttt{recognize(A, 0, 3, "abbbb")}$$ returns 0.
$$\texttt{recognize(A, 0, 3, "cba")}$$ returns 0.
$$\texttt{recognize(A, 0, 3, "a")}$$ returns 0.

typedef struct {
	int V;
	int E;
	char **Adj; // since we need 2 dimensional matrix
} automata;

int recognize(automata * A, int start, int end, char* string)
{
 	int v;
	if(string[0]=='\0' && start==end)
		return 1;
	for (v = 0; v < A->V; v++) {
		if (A->Adj[start][v]==string[0])
			if(recognize(A, v, end, string+1)==1)
				return 1;	
	}
	return 0;
}

automata* read() {
	int i, u, v;
	char w;
	automata* G=(automata*) malloc(sizeof(automata));
	printf("Enter the number of Vertices: ");
	scanf("%d", &G->V);
	printf("Enter the number of Edges: ");
	scanf("%d", &G->E);
	G->Adj = (char **)malloc(G->V * sizeof(char*));
	for (u = 0; u < G->V; u++)
		G->Adj[u] = (char *)malloc(G->V * sizeof(char));

	for (u = 0; u<G->V; u++)
		for (v = 0; v<G->V; v++)
			G->Adj[u][v] = '*';
	for (i = 0; i < G->E; i++) {
		printf("Enter the edge and the weight: ");
		scanf("%d %d %c", &u, &v, &w);
		G->Adj[u][v] = w;
	}
	return G;
}

void test(){
	automata* A = read();
	if(recognize(A, 0, 3, "aabbbbbbc")==1)
		printf("aabbbbbbc recognized");
	else
		printf("aabbbbbbc not recognized");
	
	
}

void main()
{
	test();
	getch();
}

/*

4
7
0 0 a
0 1 b
0 2 b
0 3 c
1 3 c
2 2 b 
2 3 c

*/