CPSC445 - Assignment 5 (covers Module 7)

released: Thu, 03/11/27; due: Tue, 03/12/09

NOTE: Only CPSC 445 students are expected to do this assignment.

Implementation Problem: P-System Simulator [20 marks]

In this assignment, you will implement a basic simulator for P-systems. As references, please use Holger's lecture notes and "A Guide to Membrane Computing" by Gheorghe Paun and Grzegorz Rozenberg: A Guide to Membrane Computing.

Implementation language is Java, C++, or C. In addition to the deliverables listed in the individual parts below, please submit your complete and compilable sources and a complete compiled version (for Java: ideally one single *.jar file; for C/C++: Linux or Windows executable).

(a) Implement the basic P-Systems simulator. The programme should read the following information from an input text file

list of symbols (= alphabet V)
definition of membrane structure
a set of rules for each membrane
the initial set of strings for each membrane

The syntax of the input is illustrated in the sample input file sample1-in.txt. At the end of a run, the simulator should output the symbols exported from the skin membrane and the number of steps after which the computation halted. (Example: "Computation halted after 20 steps, result: 3*a 5*b 1*e'.")

Note: Implement the simple variant of P-Systems presented in class, i.e., do not support any form of import, dissolution of membranes, or rule prioritisation. Implement non-deterministic choices as uniform random selection from the respective sets. (Example: if you have one copy of "c", but two rules that can be applied to it, each of the rules is chosen with equal probability 1/2.)

To demonstrate that your programme works correctly, run your simulator on input file test1-in.txt and report the end result; also show a trace that after each step lists the contents of all membranes (i.e., the symbols directly contained in each respective membrane).

[15 marks]

(b) Extend your programme in such a way that the absolute number and concentration of symbols in certain membranes can be measured over the course of a computation. The syntax of the extended input is illustrated in the sample input file sample2-in.txt. The measurements should be reported in the form of one file for each membrane in which measurements are taken. These files should contain one line for each computation step, in which the step number is followed by a list of the measurement values for the respective membrane; the values in this list should be separated by white space (tab and/or space characters). An (fictitious) example of the output format is given in sample output file membrane-S-out.txt.

To demonstrate that your programme works correctly, run your simulator on input file test2-in.txt and report the output files. (If you want to do this extra nicely, additionally plot the curves using gnuplot or excel.)

[10 marks]

(c) Design an input for your P-System simulator that starts with k copies of symbol a in one membrane and m copies of symbol a in another membrane and halts after outputting exactly 2k+m copies of symbol b.

[5 marks]

(d) Bonus question: Can you design an input for your P-System simulator that (deterministically or nondeterministically) oscillates between two states in which the concentration of a symbol a is low and high, respectively? (This system may never halt.)

[8 bonus marks]

General remarks:

While cooperation between students - especially between CS and non-CS students - is encouraged, each student is expected to work out the actual solutions to the problems individually and hand in their own assignment. In other words: help each other, but do not copy solutions.
Bonus marks can be used to make up for missed marks in other parts of this or any of the previous assignments.
Feel always free to contact Holger, Alena, or Dan if you feel you need further help than can be provided by your fellow students.
The assignment has to be handed in on the date it is due before 18:00. Handin is via e-mail to Holger (hoos@cs.ubc.ca).
This assignment should take you about 8-12 hours of work, if you have good knowledge of the topics covered. However, don't wait until the last minute relying on this estimate - it might not apply to you (or anyone at all), you might need additional time to consult the literature, ...