Three peace of code in C

COMP 2103X1 Assignment 5 Due Thursday, October 8 by 7:00 PM

General information about assignments (important!): http://cs.acadiau.ca/~jdiamond/comp2103/assignments/General-info.html

Information on passing in assignments: http://cs.acadiau.ca/~jdiamond/comp2103/assignments/Pass-in-info.html

Information on coding style: http://cs.acadiau.ca/~jdiamond/comp2103/assignments/C-coding-style-notes

[1] A (deterministic) finite automaton (DFA) M is a quintuple

M D .Q;†;ı;q0;F/

where — Q is a finite set of states — † is a finite set of symbols — ı W Q�† ! Q is a transition function mapping a (state, symbol) pair to a state — q0 2 Q is the initial state — F � Q are the final states

A DFA M acts on an input string S D s1s2 : : :sm as follows: starting in state q0, M reads the first symbol of S (i.e., s1) and moves into state ı.q0;s1/. Call this state x1; M next reads s2 and moves into state ı.q0;x1/. M continues in this way until it gets to the last symbol of S. After the final state transition, suppose that M is in state y. If y 2 F , then M halts in an accepting state, otherwise M halts in a non-accepting state.

DFAs are used in many places in Computer Science and related fields. For example, when sending data on “unreliable” communication lines, a common approach is to send an extra bit with every 8-bit byte, where the extra byte is chosen so that the total number of “1” bits is odd (this is called “odd-parity”). As an example, to send “A” (which has code 65 D 010000012), the extra bit would need to be a “1” bit, and consequently 010000011 would be transmitted.

At the receiving end, a check is made to ensure that every 9-bit set has an odd number of “1” bits. This can be done with a DFA defined by

Q Dfq0;q1g

† Df0;1g

F Dfq1g

and ı given by the following table: ı 0 1

q0 q0 q1

q1 q1 q0

1

Tracing this DFA’s action on the input string “010000011”, we see that the DFA starts in state q0, stays in state q0 upon reading the first 0, then moves to q1 (on reading the first 1), stays in q1 for the next 5 symbols (all 0’s), then moves to q0, (on the second-last 1), then moves to state q1 (on the last 1). Having run out of input, the DFA halts. In this case, since it halts in state q1 and q1 2 F , we say “the DFA halted in an accepting state”, or “the DFA accepts the string 010000011”.

For simple finite automata, it is often convenient to draw a picture such as the one below, to trace out the operation of the automaton. Each state of the finite automaton gets a circle. The double circle for state q1 indicates that q1 is a final state. The labelled arcs indicate the state transformations (ı) as a function of the input symbols. You might like to try inputting various binary strings (such as “010000011”) to this DFA, to convince yourself that it properly implements an odd-parity check.

q0start q1

0 1

0

1

Now that you know that, on to the actual problem.

Write a program which reads in a description of a DFA (see below) and then an input string, and outputs “Accepted” or “Not accepted” depending on whether or not the given DFA would accept the input string. The description of the DFA is given as follows: — the number of states (i.e., jQj) (the states are numbered from 0 to jQj�1) — the number of final states (i.e., jF j) — the number of symbols in † (i.e., j†j) — jF j numbers, the final states — j†j symbols (any white space char is significant, standing exactly for itself, so there will not

be multiple spaces in this list) — the transition table, given as a jQj� j†j array of numbers.

For example, the DFA shown above would be input as 2

1

2

1

01

0 1

1 0

Notes: (1) You don’t need to do careful checking of the input, and except in the one case noted below,

the exact line format of the data is not significant. Thus you don’t need to do a lot of input checking, like you might have done in other problems. (But you should still check for EOF and invalid numeric input so that your program won’t go into an infinite loop on bad input!)

2

(2) You may assume the symbols start on a new line, so after reading the final states you may skip to EOL, discard the \n, and then read j†j symbols.

(3) The description of ı above is a bit ambiguous, but (for example) a DFA with two states (which are necessarily numbered 0 and 1) with † Dfa;b;cg, the input might look like this

0 1 1

1 1 0

which means, for example, that ı.q0;a/ D q0, ı.q0;b/ D q1 and ı.q0;c/ D q1. (4) The input string (which is on the line immediately following the description of the DFA) ends

at “\n” if “\n” is not a valid input symbol, otherwise the string ends at EOF. (5) State 0 is always the initial state.

For the purposes of this assignment, do not feel you must come up with an efficient algorithm to compute the next state from the current state and the current input symbol. A straightforward solution will be fine in this case.

In the assignments directory you can find a start on this program. Feel free to take it and extend it into a solution. If you do so, however, you must leave my name as one of the authors. If you want to challenge yourself to come up with a solution without that hint, go ahead (but we can’t give you any bonus marks for doing that, sorry).

NOTE: if you do think about what you are doing, there isn’t a huge amount of code to add to the start I made up. However, if you don’t think about what you are doing, you could be working on this for a long time. “Think twice, code once.”

To give you another example, here is a diagram of a finite automaton which accepts all strings which have exactly one ‘a’ immediately followed by either any number of ‘b’s or any number of ‘c’s:

q0start

q1

q2

q3

q4

q5 a

b,c

a,b,c

b

c

a

a,c

b

a,b

c

a,b,c

The careful reader will not that states q1 and q5 are essentially the same; I used two states instead of one to avoid having lines crossing or long curved lines in the picture. (Also, both of these states have the property that once the automaton enters either of these states, it remains there forever; such states are sometimes referred to as “dead states”.)

Here is the state transition table for this automaton:

3

ı a b c

q0 q2 q1 q1

q1 q1 q1 q1

q2 q5 q3 q4

q3 q5 q3 q5

q4 q5 q5 q4

q5 q5 q5 q5

The data file for this automaton (not including any string the automaton is to process) would be as follows:

6

3

3

2 3 4

abc

2 1 1

1 1 1

5 3 4

5 3 5

5 5 4

5 5 5

I will provide some test data files for you in a few days. (My apologies to those who finish their programs and hand them in before the absolute last minute!) In the interim, make up a couple of test data files yourself. You must run your programs on all of the supplied test data files when creating your script file. You might like to draw diagrams of those DFAs to see if you can figure out what they “compute”.

If you want to learn more about DFAs and their friends (PDAs and TMs), you should take COMP 3413.

[2] Write an int function named printWedge() which takes two parameters, an int size and a char type. If size is less than 1 or greater than 25, then printWedge() should output nothing. Otherwise, the function must display a triangle of numbers drawn in a triangle with size rows and size columns (except for the optional centered version, see below). The first row includes all numbers from 1 to size. Each succesive row shows one less number, until the bottom row shows only one number, size. In order to make the appearance as “regular” as possible, all numbers should be printed in the same field width.

If type is ’r’, the triangle is as shown in the first example below. If type is ’l’, the triangle is as shown in the second example.

For two bonus points, write printWedge() so that if type is ’c’, all of the rows below the first row are centered (as well as possible) with respect to the first row (see the third sample).

4

You must write a main program which prompts the user for a number and the wedge type; there must only be one prompt, and only one input statement to read both values. Then main() should call printWedge() to do the work.

Examples (user input in red): $ a5p2

What size and type of wedge do you want? 6 r

1 2 3 4 5 6

2 3 4 5 6

3 4 5 6

4 5 6

5 6

6

$ a5p2

What size and type of wedge do you want? 4 l

1 2 3 4

2 3 4

3 4

4

$ a5p2

What size and type of wedge do you want? 3 c

1 2 3

2 3

3

printWedge() should return 0 on success and a non-zero number if it was not able to comply with the request. Q: what, if anything, should your main() do with this return value?

You should do basic error checking of the user input, but you don’t need to perform heroic deeds for this question.

[3] Your careless partner has messed up another task, and you have to carry the weight again. He was supposed to make a file with people’s names and ages, one person per line, with a tab between them. But he forgot to put the tab in. While you could spend time with an editor fixing the file, you recognize it is not only more fun, but faster, to write a5p3 to fix this problem.

Your program has two modes of operation. In the first mode, your program takes two filenames as command-line arguments. The first file is the input file with the incorrect data, and the second is the name of the output file which is to contain the corrected data. In the second mode, the first command-line argument is “-i” (for “in-place”) and the second argument is the name of the file to be modified. (It turns out that in cases like this you can’t write to the same file you are reading, so you will need to think a bit. If you can’t figure out a way to do this, you will lose only three points.)

If you choose to implement the in-place functionality, your program absolutely must (i) not delete or modify any already-existing file (except, of course, for the data file to be

modified), and

5

(ii) remove any temporary files it creates.

You may find the mkstemp() library function useful.

The problem with confirming that the output of your program is correct is that a tab can look like one or more spaces if you just cat the file to the screen. However, the od program can be used to give a more definite display of the contents of a file (see below).

Here is a sample run of your prgram, with user input in red:

$ ls -a

./ ../ a5p3 data.in

$ cat data.in

Danny Smith42

Sally Jones21

Paulina Chin30

Georges LaFleur52

Gita Khosraviani19

Patty O’Furniture88 $ a5p3 data.in data.out

$ od -c data.out

0000000 D a n n y S m i t h \t 4 2 \n S

0000020 a l l y J o n e s \t 2 1 \n P a

0000040 u l i n a C h i n \t 3 0 \n G e

0000060 o r g e s L a F l e u r \t 5 2

0000100 \n G i t a K h o s r a v i a n

0000120 i \t 1 9 \n P a t t y O ’ F u r 0000140 n i t u r e \t 8 8 \n

0000152

$ cmp data.in data.out

data.in data.out differ: byte 2, line 1

$ a5p3 -i data.in

$ cmp data.in data.out

$ ls -a

./ ../ a5p3 data.in data.out

Note 1: this use of od (see man od) shows that the file actually contains tab characters.

Note 2: the cmp program compares two files and (when called with no options) either reports the first place where the files differ, or, if they are the same, outputs nothing at all. In this sample, cmp confirms that after the first running of your program data.in was not the same as the (correct) output file, but after the second running of your program it was. This makes it easier for you (and the marker as well) to know that your program worked correctly than if you display all of the files with od -c.

Your program must not clutter up your directory with files. (Use ls -a before and after to show that no new files are (permanently) created by your program.)

As always, when reading from or writing to files, you must check fopen()’s return value before

6

doing anything at all with the file pointer. And, of course, you must do sensible things when the return value indicates you were not able to open the file. When you create your script file you should show a test where the attempt to open the input file fails, and a test where the output file can’t be opened.

Design note: any solution which assumes it can read the whole file into memory is doomed, because I may send you a 50 GB file to process.

Question: what possible error situations could your program run into? Does your program handle them? Does you testing test each of these possible situations? (It should!) You will need to do more than one run of your program, but all runs should show all the tests as above.

Note: your program may assume that every line in the input file has a name followed by an age.

Did you use functions in any of these questions? Should you have? Did you document them correctly?

Does you program “blow up” on unexpected input, or does it deal with bad input in a “graceful” way?

How does your program deal with boundary conditions, if there are any?

Did you remember to put all required comments in? Does your program call out for any other comments in the body of the code?

7