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

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: