# Automata theory, grammars and languages

Hi Brian:

Total points earned (rounded): 60 out of 150 (40%).

Task Requirements points earned: 9.38 out of 37.5 (25%).

Demonstration and application of knowledge points earned: 20.63 out of 82.5 (25%).

Academic writing and format points earned: 30 out of 30 (100%).

Strengths: Part IV: Good job with the transition table. The states are locked and unlocked. The input is token or push. This was represented in a table. Good job representing this in a digraph. Great job with parse tree. The leaves of the tree are congruent with the given expression E = (p+q) X p-r X p/(q+q).

Opportunities for improvement: You did not complete Parts I-III.

**Task Background:**This assignment involves solving problems by using various discrete techniques to model the problems at hand. Quite often, these models form the foundations for writing computer programming code that automate the tasks. To carry out these tasks effectively, a working knowledge of sets, relations, graphs, finite automata structures and Grammars is necessary.

**Part I: Set Theory**

Look up a roulette wheel diagram. The following sets are defined:

- A = the set of red numbers
- B = the set of black numbers
- C = the set of green numbers
- D = the set of even numbers
- E = the set of odd numbers
- F = {1,2,3,4,5,6,7,8,9,10,11,12}

From these, determine each of the following:

- A∪B
- A∩D
- B∩C
- C∪E
- B∩F
- E∩F

**Part II: Relations, Functions, and Sequences**

The implementation of the program that runs the game involves testing. One of the necessary tests is to see if the simulated spins are random. Create an n-ary relation, in table form, that depicts possible results of 10 trials of the game. Include the following results of the game:

- Number
- Color
- Odd or even (note: 0 and 00 are considered neither even nor odd.)

Also include a *primary key*. What is the value of *n* in this *n*-ary relation?

**Part III: Graphs and Trees**

Create a tree that models the following scenario. A player decides to play a maximum of 4 times, betting on red each time. The player will quit after losing twice. In the tree, any possible last plays will be an ending point of the tree. Branches of the tree should indicate the winning or losing, and how that affects whether a new play is made.

**Part IV: Automata Theory, Grammars and Languages (There are 2 questions for this part)**

(1) 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.

## We've got everything to become your favourite writing service

### Money back guarantee

Your money is safe. Even if we fail to satisfy your expectations, you can always request a refund and get your money back.

### Confidentiality

We don’t share your private information with anyone. What happens on our website stays on our website.

### Our service is legit

We provide you with a sample paper on the topic you need, and this kind of academic assistance is perfectly legitimate.

### Get a plagiarism-free paper

We check every paper with our plagiarism-detection software, so you get a unique paper written for your particular purposes.

### We can help with urgent tasks

Need a paper tomorrow? We can write it even while you’re sleeping. Place an order now and get your paper in 8 hours.

### Pay a fair price

Our prices depend on urgency. If you want a cheap essay, place your order in advance. Our prices start from $11 per page.