Ryerson University

Due: Tuesday March 30

Important Notes

Notes on Programing Tasks

This assignment includes a programing question which will be auto marked. It is thus very important that you consider the following:

Part 1 - Recursion and Structural Induction


The family of Central Graphs is defined recursively below. Each Central graph has a head and each vertex of a Central graph has an integer associated with it called its saturation. These are also defined recursively within the definition.

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


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.

i.e. xV(G) is a tail if and only if sG(x) < 2.

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 G1 = (V1, E1), G2 = (V2, E2) and G3 = (V3, E3) with ViVj = ∅ whenever ij and let a1, a2 and a3 be the heads of G1, G2 and G3 respectively and let b be a tail of G1.


    G = (V, E), where V = V1V2V3 and E = E1E2E3 ∪ { ba2} ∪ { ba3}
    is also a central graph with head a1 and
    sG(x) =
    sGi(x) + 1 if x = ai, i = 2, 3.
    sG1(x) + 2if 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.


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

  2. Take the Central graphs from Example 1 as G1, G2 and G3 in ii. This yields a new Central graph:

    G = ({a1, a2, a3}, { {a1a2 }, {a1a3} }),
    a1 is the head, s(a1) = 2 and s(a2) = s(a2) = 1, thus a2 and a3 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:
    ({a1, a2, a3, a1', a2', a3', b}, { {a1a2 }, {a1a3}, {a1'a2' }, {a1'a3'}, {a2b}, {a2a1'} } ).

    where a1 is the head and s(a1) = 2, s(a2) = s(a1') = 3 and s(a3) = s(a2') = s(a3') = s(b) = 1, so a3, a2', a3', and b are tails.

  4. Alternately, taking the graphs in a different order, and using H as the head (G1) in ii, we get
    ({a1, a2, a3, a1', a2', a3', b}, { {a1a2 }, {a1a3}, {a1'a2' }, {a1'a3'}, {ba1}, {ba1'} } ).

    where b is the head and s(b) = 2, s(a1) = s(a1') = 3 and s(a2) = s(a3) = s(a2') = s(a3') = 1, so a2, a3, a2' and a3', are tails.


  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:


Part 2 - Regular Languages and FSA's


For this question ε is the empty string. Define the following sets:
OP = { &&, ||, ^, == }
DIGIT = [0-9]
LETTER = [A-Za-z]
WHITE = [Space, Tab, ε ]

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

INTEGER = Any number of DIGITS, but must have at least one DIGITS.
IDENTIFIER = Any number of LETTERS or DIGITS, but must begin with a LETTERS.
Any member of IDENTIFIER or INTEGER is a member of BOOLEAN.

If x and y are strings in BOOLEAN, then so is


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

For example, the following are in BOOLEAN:

axy, a && x || y, a ^ 12, 12 || a && beryl34.

The following are not in BOOLEAN:

1x && 124, x &&, (12 && 3) || 3.



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

  2. 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.

  3. 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:

    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') . . .

  4. 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.

    If x and y are strings in BOOLEAN, then so is

    and so is

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

Hand in

This page is maintained by Peter Danziger.
Last modified Tuesday, 30-Mar-2010 06:51:35 EDT