Assignment: Introduction to Theory of Computing

Course Project : Design An Automatic Selling Machine

Problem: Design a machine selling three types of drinks dl, d2, d3 and two types of stacks sl, s2. The buyers can use three types of coins cl, c2, c3. The number of each drink or snack that a buyer can buy once from the machine is nl, n2. Suppose that in the machine there are places for inserting coins, selecting the type of the drinks or snacks, and picking the number of the drink or stack that the buy selected. At the end the buyer has to push a button S to start the buying process. A buyer has to follow the order you designed when he/she buys drinks or snacks, e.g., first insert coins, then select the type of drinks or snacks, then pick the number of the drink or snack that the buyer selected, and finally push the button S to start the process; or he/she can repeat the same process before push the button S. Design the machine with the following stages:

(1) Suppose that X = {cl,c2,c3,s1,s2,d1,d2,d3,n1,n2,S} . Design the regular expression r such that L(r) is the language which contains the strings that buyers enter the machine.

(2) Design a NFA which accept the language L(r) in (1).

(3) Design a regular grammar to generate the language equivalent to L(r) in (1)

(4) Convert the NFA to DFA

(5) Implement the DFA in (4) use C# .

Requirement for the project:

- The report contains: (i) the requirements of the machine, (ii) detailed explanation for each of (1), (2), (3), (4), (iii) Code for (5), (iv) testing page which shows that the machine accepts the strings that belong to L(r) and reject the strings which don't belong to L(r) .

- Give a power point presentation.