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

Contents


    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.

Formulae and Definitions in Alphabetical Order