/* 
 * This program generates a random 5-state finite state automaton over
 * the alphabet {a, b}, using the first command line argument to seed
 * the random number generator.
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NUM_STATES	5
#define ALPHABET_SIZE	2
#define INITIAL_STATE	0
#define FINAL_STATE	(NUM_STATES-1)
#define MAX_EXAMPLES	100

int	fsa_states[NUM_STATES][ALPHABET_SIZE];	/* array of states */
char	yes_examples[MAX_EXAMPLES][1000],	/* yes example strings */
	no_examples[MAX_EXAMPLES][1000];	/* no example strings */

/* this function move the string parameter to the next string in 
 * lexicographic order
 */
void increment_string (char *s) {

	/* if null string, set it equal to "a" */

	if (!s[0]) {
		s[0] = 'a';
		s[1] = 0;
	} else if (s[0] == 'a') 

	/* if the first character is 'a', make it 'b' */

		s[0] = 'b';
	else {

	/* otherwise, recursively increment the rest of the string */

		s[0] = 'a';
		increment_string (&s[1]);
	}
}

/* make a raindom fsa *

void randomize_fsa (void) {
	int	i, j;

	for (i=0; i<NUM_STATES; i++) 
		for (j=0; j<ALPHABET_SIZE; j++) 

			/* initialize each element to a random number
			 * between 0 and NUM_STATES 
			 */
			fsa_states[i][j] = rand () % NUM_STATES;
}

/* decide whether the fsa accepts the string s */
int accepts (char *s) {
	int	i, state, index;

	/* start out in the initial state */

	state = INITIAL_STATE;

	/* let i index the string from first to last character */

	for (i=0; s[i]; i++) {

		/* get the ordinal value of the character  (a=0, b=1, ...) */

		index = s[i] - 'a';
	
		/* move to the state indicated in the array */

		state = fsa_states[state][index];
	}

	/* if the current state is the final state, return true else false */

	return state == FINAL_STATE;
}

/* this function counts the number of strings, up to the limit n, accepted
 * by the fsa
 */
int count_accepting (int n) {
	int	i, count;
	char	s[1000];

	count = 0;

	/* start out with the empty string */

	s[0] = 0;

	/* do this n times */

	for (i=0; i<n; i++) {

		/* get the next string in lexicographic order */

		increment_string (s);

		/* add one to count iff the string is accepted */

		count += accepts (s);
	}
	return count;
}

/* this function prints the yes and no sample strings */

void print_examples (int n) {
	int	i, j, k;
	char	s[1000];

	i = 0;

	/* start out with the empty string */

	s[0] = 0;

	/* k will count rejected strings, j will count accepted strings,
	 * counting backwards from n
 	 */

	k = j = n;

	/* while either j or k is not zero... */

	while (j || k) {

		/* get the next string */

		increment_string (s);

		/* with probability 0.3, check this string for
		 * acceptance and add it to our examples
		 */
		if (rand () % 10 < 3) {
			if (accepts (s)) {

				/* decrement j if we accept the string */

				if (j) strcpy (&yes_examples[--j][0], s);
			} else {

				/* decrement k if we reject the string */

				if (k) strcpy (&no_examples[--k][0], s);
			}
		}
	}

	/* print a table with the examples */

	printf ("%20s\t%20s\n", "yes examples", "no examples");
	printf ("%20s\t%20s\n", "------------", "-----------");

	/* print the examples backwards, since they are placed in 
	 * the arrays backwards
	 */
	for (i=n-1; i>=0; i--) {
		printf ("%20s\t%20s\n", yes_examples[i], no_examples[i]);
	}
}
	
/* main function */
int main (int argc, char *argv[]) {
	int	i, seed, count;

	/* if wrong number of args, complain and exit */

	if (argc != 2) {
		fprintf (stderr, "Usage: %s <login-name>\n", argv[0]);
		exit (1);
	}

	/* the seed to srand() will be the sum of digits in the login
	 * name, so each student has a unique (hopefully) seed
	 */
	seed = 0;
	for (i=0; argv[1][i]; i++)
		seed += argv[1][i];

	/* seed the random number generator */

	srand (seed);

	/* make a random fsa */

	randomize_fsa ();

	/* count the number of strings out of 100 accepted by this fsa */

	count = count_accepting (100);

	/* while that number is less than 30 or greater than 60... */

	while (count < 30 || count > 60) {

		/* ...get a different fsa */

		randomize_fsa ();
		count = count_accepting (100);
	}

	/* print the fsa rules in a table */

	printf ("state#\ta\tb\n");
	for (i=0; i<NUM_STATES; i++) {
		printf ("%d\t%d\t%d\n", i, fsa_states[i][0], fsa_states[i][1]);
	}

	/* print the example strings */

	print_examples (10);
	return 0;
}