[CSUSB] >> [CompSci] >> [Dick Botting] >> [CS656/556 Course Materials] >> train2
[Index] || [Contents] || [Grades] Tue Aug 5 11:45:02 PDT 2003

# The Goods Train Problem -- Solutions

A train starts with an engine and ends with a caboose. In between the engines and the caboose there are zero or more carriages.

A two-engined-train has two engines in front else there is one engine in front.

Express the possible sequences of trains using the XBNF notation and the given symbols:

1. carriage::=given.
2. engine::=given.
3. caboose::=given.

# Solution 1

4. train::= engine O(engine) #carriage caboose.

Very short and simple but hides the difference between one and two engined trains.

# Solution 2

5. train::= one_engined_train | two_engined_train.
6. one_engined_train::=engine #carriage caboose.
7. two_engined_train::=engine engine #carriage caboose.

More complex but has all the terms in the problem.

# Solution 3

8. train::= engine #carriage caboose | engine engine #carriage caboose.

Shows the structure well but not the terminology.

# Solution 3

9. train::= (engine | engine engine )#carriage caboose.

Short.

# Solution 3

10. train::= engines #carriage caboose.
11. engines::= engine | engine engine.

# New Exercise 1

Suppose the second train.... if it exists is after the last carriage and before the caboose.

# New Exercise 2

Suppose the second train.... if it exists is after the last carriage and before the caboose. Also each carriage is refrigerated or not refrigerated.

# Glossary

12. O::=Option, See XBNF below.
13. XBNF::= See http://www.csci.csusb.edu/dick/maths/intro_ebnf.html.