CSc 352: Assignment-6: Input/Output

Due Monday, July 29- 3pm

The assignment name for turnin is cs352_hw6

1- Dictionary Lookup

Standard telephone keypads contain digits 0 through 9. The numbers 2 through 9 each have three letters associated with them. (2:ABC, 3:DEF, 4:GHI, 5:JKL, 6:MNO, 7:PRS, 8:TUV, 9:WXY) Many companies try to get 7-digit phone numbers so that the letters associated contain keywords reminding the company (CALLATT, GORYDER, etc.). You are to write a function called find_words with the following prototype:

void find_words(int numbers[]);

where numbers is an array of integers (each with 7 digits), and the last number inside the numbers[] array is 0, to indicate the end of the array. The function takes each number inside the array and prints out all the meaningful(*) 7-letter words corresponding to that number. If the array contains only the numbers 2244383, and 3228679 your output should look like:

2244383
-------
ACHIEVE
...       (Allthe other words, I don't exactly know) 
3228679 
------- 
FACTORY 
...       (All the others..) 

The words/phrases printed out for each number should be in sorted order.

meaningful(*): You will basically lookup the dictionary file /usr/share/lib/dict/words on lectura. Any word in that file is meaningful.

Put your functions in a file named findword.c

Note: %60 of the points for this question is based on correctness. The rest is based on how fast your program runs. So make it efficient in whatever way you can. But first make it correct, an incorrect program that is the fastest will not get you any of the %40 either.

Extra: Do it for words/phrases, not only for words. Meaningful phrases are constructed from meaningful words (that have at least 2 letters), i.e. any combination of the words in that file. So the number 4425626 corresponds to the meaningful(*) word HICKMAN, and to the meaningful (*) phrase HIALMAN - since HI, AL, MAN are all by themselves meaningful(*).) If the array contains only the numbers 4425626, and 8432677 your output should look like:

4425626
-------
HIALMAN
HICKMAN
...            (Allthe other words/phrases, I don't exactly know) 
8432677
-------
THEBOSS
...            (All the others..) 

Put your functions for the extra part in a file named extrafindword.c

2- Finite State Machines

Write a C program, in a set of files as described below, that simulates a finite state machine.

Invocation:

Your program will be invoked with a single argument, which is the name of a file specifying a finite state machine, as described below. If no argument is specified, or if the argument does not correspond to a readable file, the program should give a descriptive error message indicating the problem (print to stderr in the latter case) and exit with status -1.

Format of a Finite State Machine Specification File:
Each line of the file specifies some aspect of the finite state machine. The first letter of the line is one of s, t, or f, and indicates the ``type'' of that line, i.e., the structure of the rest of the line and its meaning. These are as follows:

We assume the convention that the very first state named in the input file with a line ``s stateName'' is the start state. Notice that the alphabet of our finite state automata, i.e., the symbols that can appear in the inputs to our automata, is fixed as the set {0, 1, ..., 9}.

Example (described in more detail here) :

Input FileFinite State Machine
s a
s b
t a b 1
t a a 0
t b b 0
t b a 1
f b

Notice, in this example, that while the input file specifies only transitions on the symbols 1 and 0, the input alphabet is nevertheless the entire set {0, 1, ..., 9}. This means that an input to this finite state machine can contain symbols, such as 5 or 8, for which no transitions are specified. Such inputs are not erroneous: they are simply not accepted by the automaton.

Input:

Your program will repeatedly read input strings (each input string is a sequence of digits with no intervening whitespace) from stdin; simulate the behavior of the finite state machine on each such input string, in each case starting at the start state of the machine; and print the result on stdout, as follows: a 1 is printed if the finite state machine is in a final state when the entire input string has been processed; a 0 is printed otherwise.

Example: Suppose that infile0 is the input file shown above, and that the file queryfile contains:

10011
1001
100
1011000
9876
Then, executing
fsa_sim infile0 < queryfile
should print out the following:
1
0
1
1
0
This states that the first, third, and fourth strings are accepted by the finite state machine while the second and fifth are not.

Files to be turned in:

You should structure this program into files as follows:

Turn in the following files for this problem: fsa.h, fsa_read.c, fsa_sim.c, and Makefile.

You may assume that an input line is at most 1024 characters long, and that the name of any state is at most 64 characters. You may also assume that the input file and queries do not contain formatting errors. There should not be any fixed hard limits on the input, e.g., the number of states or transitions, or the number of queries allowed. Moreover, the amount of memory used by your program should be proportional to the size of the input.

The executable file /home/cs352/SUMMER02/assignment6/samplefsa_sim is S. Debray's solution to the problem: you can use it to check your code. The file

/home/cs352/SUMMER02/assignment6/infile0

is a sample input file, while

/home/cs352/SUMMER02/assignment6/query00

is a sample query file.