MTH210	Assignment
		Due: Tuesday March 30

Important Notes

• This assignment is worth 10% of the course mark.
• You are allowed to work on this assignment in groups of 1, 2, 3 or 4. Each team only hands in one assignment for the whole team. All the members of the group must be listed on the assignment.
  Please read the MTH210 General Assignment Information and Teamwork and Cheating Policy before submitting your assignment.

Notes on Programing Tasks

• Your programs should be submitted using the submit-mth210 command on one of the moons. If none of your team members have access to the moons see me.
• You can resubmit your files up to the deadline, but if you resubmit after that date marks will be deducted for lateness. Only the last submission will be considered.
• If your program does not compile you will recieve a grade of 0.
• Your program must have the filename specified, otherwise it will not compile and you will receive a grade of 0.
• Submit only those files required. Do not use multiple files or make files.
• Read the instructions carefully, use the input provided, with appropriate error checking, and provide the output required.
• All programs must be in C, they will be compiled with gcc. Therefore check that your program compiles correctly. (Note that the gnu compiler, gcc, is slightly more forgiving than the strict cc compiler.)

Part 1 - Recursion and Structural Induction

Preamble

Given a vertex x of a Central graph G, we denote the saturation of x in G by s_G(x). We drop the G if it is clear from context.

Definition

Some of the vertices of a central graph are called tails, according to the following definition:
Any point with saturation less than 2 is a tail.

Recursive Definition

1. Base

   The empty graph of order one is central. i.e. G = ({a}, ∅) is a central graph. a is the head and has saturation s(a) = 0.
   (Note that this means that a is both a head and a tail.)

2. Recursion (There is only one recursive rule)

   Given Central three graphs G₁ = (V₁, E₁), G₂ = (V₂, E₂) and G₃ = (V₃, E₃) with V_i ∩ V_j = ∅ whenever i ≠ j and let a₁, a₂ and a₃ be the heads of G₁, G₂ and G₃ respectively and let b be a tail of G₁.

   Then

   G = (V, E), where V = V₁ ∪ V₂ ∪ V₃ and E = E₁ ∪ E₂ ∪ E₃ ∪ { ba₂} ∪ { ba₃} is also a central graph with head a₁ and

   sG(x) =

   sGi(x) + 1 if x = ai, i = 2, 3. sG1(x) + 2 if x = b sGi(x) otherwise and x ∈ V(Gi)

3. No graph other than those obtained by repeated applications of i - ii above is a Central graph.

Examples

1. By Rule i, G_i = ({a_i}, ∅) is a Central graph for each i = 1, 2, 3, with head a_i and s(a_i) = 0.

2. Take the Central graphs from Example 1 as G₁, G₂ and G₃ in ii. This yields a new Central graph:
   G = ({a₁, a₂, a₃}, { {a₁a₂ }, {a₁a₃} }), a₁ is the head, s(a₁) = 2 and s(a₂) = s(a₂) = 1, thus a₂ and a₃ are tails.

3. We may now apply rule ii again, this time using two copies of G from Example 2 above (G and G') and another base case H = ({b}, ∅) to produce the following: ({a₁, a₂, a₃, a₁', a₂', a₃', b}, { {a₁a₂ }, {a₁a₃}, {a₁'a₂' }, {a₁'a₃'}, {a₂b}, {a₂a₁'} } ).
   where a₁ is the head and s(a₁) = 2, s(a₂) = s(a₁') = 3 and s(a₃) = s(a₂') = s(a₃') = s(b) = 1, so a₃, a₂', a₃', and b are tails.

4. Alternately, taking the graphs in a different order, and using H as the head (G₁) in ii, we get ({a₁, a₂, a₃, a₁', a₂', a₃', b}, { {a₁a₂ }, {a₁a₃}, {a₁'a₂' }, {a₁'a₃'}, {ba₁}, {ba₁'} } ).
   where b is the head and s(b) = 2, s(a₁) = s(a₁') = 3 and s(a₂) = s(a₃) = s(a₂') = s(a₃') = 1, so a₂, a₃, a₂' and a₃', are tails.

Questions

1. Find central graphs with 11 and 13 vertices. Give a drawing of your graph.

2. Use structural induction to show that every Central graph is connected.

3. Show that every Central graph is a tree by using structural induction to show that the number of edges is always one less thatn the number of vertices.

4. Use structural induction to show that if a Central graph is not base (is not the graph from rule i), then given any point one of the following must hold:
   • it is the head and has saturation 2;
   • it is a tail and has saturation 1;
   • it is not the head and has saturation 3.

Notes

• You must use structural induction, no other method is acceptable.

• You may assume the Tree Edge Theorems (11.5.2 and 11.5.4):

  A connected graph G with n vertices is a tree if and only if it is of size n - 1.

• You may assume the Inclusion/Exclusion Rule, Theorem 6.3.3 in the book:

  Suppose the set two sets A and B satisfy |A ∩ B| = n, then |A &cup B| = |A| + |B| - n

Part 2 - Regular Languages and FSA's

Preamble

Define the following languages over the set of OP ∪ DIGITS ∪ LETTERS ∪ WHITE.

Here WHITE OP means the concatenation of an element of WHITE with an element of OP etc.

For example, the following are in BOOLEAN:

The following are not in BOOLEAN:

Notes:

• You may use the notation Σ to indicate an arbitrary element of the set Σ. Thus, for example, OP^* would indicate an arbitrary string of elements of OP, equivalent to (&& or || or ^ or == )^*.

  You may also use the UNIX [ ] notation, as above. So, for example, [0-9] would indicate the digits 0 through 9.

• Keep your strings as simple as possible.

Questions

4. Write regular expressions for the Languages INTEGER, IDENTIFIER and BOOLEAN.

5. Draw A Finite State Automaton which accepts the language BOOLEAN.

   Even though you will only be submitting the FSA for the ARITHMETIC language, it is recommended that you first draw FSAs for the other two languages, when you are sure that they work properly, integrate them into the BOOLEAN FSA.

6. Based on Algorithm 12.2.1 on page 755 of your textbook, or algorithm 12.2.2 of page 756, or otherwise, write a C program which implements the BOOLEAN FSA you drew in 2.2. Both algorithms will need substantial adaptations to work well with this particular FSA.

   Note this question while be marked independently of the previous question, if there is a mistake in your FSA above, you will lose marks here as well.

   This part of your assignment will be tested mechanically. Read the notice at the start of this assignment. Your program must meet the following requirements:

   • Your program should be in only one file, called fsa.c

   • Your program should read one string from the command line

     To do this declare your main routine as
     char a;
     int main(int argc, char *argv[]) {
     . . .
     argv[1] now points to the first command line argument.
     So, printf("%s\n", argv[1]); will print the string,
     a = argv[1][0]
     sets a to be the first character of the string, a = argv[1][1] the second and so on.
     The string is null terminated, so argv[1][i] == 0 means that you are at the end of the string.

   • Your program should return the following (return value from main):
     • 1 if the string that was read is an element of BOOLEAN
     • 0 if it isn't.
     • -1 on error.

   • If @ is given on the command line, your program should print out the group members names. A sample code that does this can be found here.

     Make sure that all group members are entered in this way. Those that are not here will not get a mark for the programming portion.

   Hint: if you want to see if a character, a is in a range use >, < and an ASCII table.

   For example, to check if x ∈ [0-9] use:
   if(x >= '0' && x <= '9') . . .

7. The ARITHMETIC language above does not allow bracketing. So (a || b) && c, would be an illegal string. We can modify the definition of BOOLEAN to allow brackets. We add open bracket '(' and close bracket ')' to the alphabet and redefine BOOLEAN to BRACKET_BOOLEAN.

   BRACKET_BOOLEAN

   =

   Base Any member of IDENTIFIER or INTEGER is a member of BOOLEAN. Recursion If x and y are strings in BOOLEAN, then so is x WHITE OP WHITE y and so is '(' WHITE x WHITE OP WHITE y WHITE ')'.

   Use the Pumping Lemma to show that the modified version of this language BRACKET_BOOLEAN is not a regular language.

Hand in

• Submit your programs electronically on one of the moons by using the command:

  submit-mth210 fsa.c

• Submit on paper a writeup of your answers to questions.
• Staple the Assignment Marking Sheet to the front of the paper component of your assignment.