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:
- s stateName
stateName is the name of a state, which is a sequence of non-whitespace characters. This has the effect of declaring a state in the finite state machine.
- t stateName1 stateName2 symb
stateName1 and stateName2 are names of states, and symb is one of the digits 0, 1, 2, ..., 9. Both of the states mentioned must have been declared earlier with a line ``s ...'' This has the effect of specifying that there is a transition from stateName1 to stateName2 on symbol symb.
- f stateName
stateName is the name of a state, which must have been declared earlier with a line ``s ...'' This has the effect of specifying that stateName is an accepting state in the finite state machine.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 File Finite State Machine s a
s b
t a b 1
t a a 0
t b b 0
t b a 1
f bNotice, 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:
10011Then, executing
1001
100
1011000
9876fsa_sim infile0 < queryfileshould print out the following:1This states that the first, third, and fourth strings are accepted by the finite state machine while the second and fifth are not.
0
1
1
0
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.
- fsa.h
Contains typedefs, macro definitions, etc., for the data structure representing the finite state machine, as well as any other definitions (but not code!) you may want.
- fsa_read.c
Contains code to read in the input file specifying the finite state machine.
- fsa_sim.c
Contains code to read in the input strings and simulate the finite state machine on each input string.
- Makefile
A makefile that will support at least the following targets:
This makefile should be careful to avoid unnecessary dependencies between files: a file should be recompiled only when necessary.
- make fsa_sim
- Causes the source files to be compiled to yield an executable named fsa_sim that implements your finite state machine simulator.
- make clean
- Causes all object files (*.o) in the current directory, as well as the file named fsa_sim (if it exists) to be deleted.
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.