application in discrete math Part IV: Automata Theory, Grammars and Languages (There are 2 questions for this part)

Question

A gate with three rotating arms at waist height is used to control access to a subway in New York City. Initially, the arms of the gate are locked preventing customers from passing through. Unlocking the arms requires depositing a token in a slot, which allows the arms to rotate to a complete turn which allows one customer to push through and enter. Once the customer passes through the arms are then locked again until another customer deposits another token in the slot.

The gate has two states: LOCKED and UNLOCKED. It also has two inputs: TOKEN and PUSH. When the gate is locked, pushing the arm of the gate has no effect regardless of how many times it is pushed. The input TOKEN changes the state from LOCKED to UNLOCKED. When the gate is in the UNLOCKED state, inserting additional tokens has no effect on the state. But when in the UNLOCKED state, a PUSH input changes the state to LOCKED.

(i). Provide a transition table showing each state, the inputs, and the resulting new states for each input

(ii). Represent your transition table into a digraph (transition diagram)

(2) Here is a context-free grammar that can be used to generate algebraic expressions via the arithmetic operators (addition, subtraction, multiplication, and division), in the variables p, q, and r. The letter E stands for expression:

Rule 1: E —› p

Rule 2: E —› q

Rule 3: E —› r

Rule 4: E —› E + E

Rule 5: E —› E – E

Rule 6: E —› E X E

Rule 7: E —› E/E

Rule 8: E —›(E)

(i). Use the above grammar to derive the string given by the mathematical expression E = (p + q) X p – r X p/(q + q)

(ii). Provide a parse tree for this derivation.                        

Answer 1

### (1) Automata Theory for the Subway Gate

#### (i) Transition Table

The transition table describes the behavior of the gate system based on its current state and inputs.

| Current State | Input | Next State |

|---------------|-------|------------|

| LOCKED | TOKEN | UNLOCKED |

| LOCKED | PUSH | LOCKED |

| UNLOCKED | TOKEN | UNLOCKED |

| UNLOCKED | PUSH | LOCKED |

#### (ii) Transition Diagram

To represent this in a transition diagram:

1. **States**: Represent the states LOCKED and UNLOCKED as circles.

2. **Transitions**:

- An arrow from LOCKED to UNLOCKED labeled "TOKEN".

- An arrow from UNLOCKED to LOCKED labeled "PUSH".

- Self-loops on LOCKED labeled "PUSH" and on UNLOCKED labeled "TOKEN".

Here is a textual representation of the transition diagram:

```

LOCKED --TOKEN--> UNLOCKED

^ |

| |

+--PUSH--<------------+

UNLOCKED --PUSH--> LOCKED

^ |

| |

+--TOKEN--<-----------+

```

(2) Context-Free Grammar and Derivation

(i) Derive the string (p + q) X p – r X p/(q + q)

To derive the expression `(p + q) X p – r X p/(q + q)`, follow these steps:

1. Start with `E` and apply the production rules to build up the expression.

```

E → E – E (Rule 5)

```

2. For the first `E`, derive `(p + q) X p` and for the second `E`, derive `r X p/(q + q)`.

```

E → (E) X E (Rule 6)

```

3. Derive `(p + q)` and `p` for the first `E`:

```

E → (E + E) (Rule 4)

```

4. Derive `p` and `q`:

```

E → p (Rule 1)

E → q (Rule 2)

```

5. Derive `r X p/(q + q)` for the second `E`:

```

E → E X E (Rule 6)

E → E / E (Rule 7)

```

6. Derive `r` and `p` for the first `E` and `(q + q)` for the second `E`:

```

E → p (Rule 1)

E → q (Rule 2)

E → (E + E) (Rule 4)

```

7. Combine all derivations:

E → (E + E) X p – E / E

E → (p + q) X p – r X p / (q + q)

(ii) Parse Tree

A parse tree visualizes the structure of the expression according to the grammar.

```

E

/|\

/ | \

/ | \

E - E

/|\ /|\

/ | \ / | \

( E ) / E \

| / | \

E X E / \

/|\ / E \

/ | \ / | \

p + q X p r / \

/ \

E E

/ \ / \

( + q q

/ \

E E

/ \

q q

```

In the parse tree:

- The root node represents the entire expression.

- Each internal node represents an operator or parenthesis.

- Leaf nodes represent the variables `p`, `q`, and `r` and the operators.

This parse tree reflects the order of operations as specified by the context-free grammar rules.