Java project based on algorithm provided

Turing machines are a universal computing model, while there are other

interesting computing models there which are sub-Turing; e.g., pushdown

automata. Furthermore, modern computer science also studies computing

models that have a root in biology and chemistry; e.g., through molecular

reactions.

Here comes a model, where we have a multiset of objects. That is, S0

is a given multiset containing 5 objects a's, 5 objects b's and 5 objects c's.

There is a given set T of three rules as follows:

abc ! aab //replace one a, one b and one c with

//two a's and one b

ac ! ba

cb ! cc

Hence, the system runs as follows. Each step changes from a multiset S to

a multiset S0, written S ! S0, as follows. The step contains a simultaneous

applications of k1 number of the rst rules, and k2 number of the second

rules and k3 number of the third rules, for some k1; k2; k3  0. The step is

therefore written as (k1; k2; k3). The step is rable on the S if the S contains

enough copies of objects to trigger the rules. That is, to re k1 number of

the rst rules, there must be k1 number of a's, k1 number of b's, k1 number

of c's in S. Similarly, S must also contain additional a's and b's and c's

for k2 number of second rules and k3 number of third rules to re. In this

case, we use (k1; k2; k3)(S) to denote the result of S after the simultaneous

applications of k1 number of the rst rules, and k2 number of the second

rules and k3 number of the third rules.

We write (k1; k2; k3) < (k01

; k02

; k03

) if k1  k01

; k2  k02

; k3  k03

and ki 6= k0i

for some 1  i  3. We say that (k1; k2; k3) is maximal-parallel on S if

(k1; k2; k3) is rable on S but (k01

; k02

; k03

) is not for any (k01

; k02

; k03

) satisfying

(k1; k2; k3) < (k01

; k02

; k03

). We write S ! S0 if S0 = (k1; k2; k3)(S) for some

(k1; k2; k3) that is maximal-parallel on S.

S can be reached in three steps if there are S1; S2 such that S0 ! S1 !

S2 ! S.

Write a program to check whether there is an S that can be reached in

three steps and in S, the number of a's, the number of b's,the number of c's

are all the same.

Algorithm C Programming C++ Programming Engineering Java

Project ID: #16645689

About the project