Automata theory, grammars and languages ip

Assignment Help Basic Computer Science
Reference no: EM13960961

Automata Theory, Grammars and Languages IP

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.

Reference no: EM13960961

Questions Cloud

Automata theory involves the study of mathematical objects : Automata theory involves the study of mathematical objects called automata and the computational problems that can be solved using them. Context-free grammar provides us with mathematical techniques of building phases in a language from other bloc..
Disadvantages of having an employer draw attention : What are advantages and disadvantages of having an employer draw attention to situations where employees use some of their work time to do non job related activities
Apply the 1st law of thermodynamics to the resistor : A 100 ohm resistor is immersed in a constant temp bath at 300 K. A current of 10 amps flows through the resistor and a steady state is achieved
Using electronic health records vs. traditional paper : Discuss some of the advantages AND disadvantages of using electronic health records vs. traditional paper charts in a medical office. Think about this from a health professional's perspective (in terms of cost, ease of use, accessibility of patient i..
Automata theory, grammars and languages ip : 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 ..
Find the planned order releases for all items : One unit of A is composed of two units of B and three units of C. Each B is composed of one unit of F. C is made of one unit of D, one unit of E, and two units of F. Items A, B, C, and D have 20, 50, 60, and 25 units of on-hand inventory, respectivel..
What is the final temperature of the aluminum : A hand help shopping basket 62.0 cm long has a 1.81 kg carton of milk at one end, and a 0.722 kg box of cereal at the other end. Where should a 1.80 kg container of orange juice be placed so that the basket balances at its center?
The materials with the lowest resistance are called : An electron is moved from point A to point B along an equipotential surface.
What is annual inventory holding cost-annual ordering cost : Ross White’s machine shop uses 2,500 brackets during the course of a year, and this usage is relatively constant throughout the year. These brackets are purchased from a supplier 100 miles away for $19 each, and the lead time is 4 days. What is the a..

Reviews

Write a Review

 

Basic Computer Science Questions & Answers

  You will be designing an on campus internetwork for new larg

You will be designing an on-campus internetwork for new large university that has been proposed. The University will have dozens of buildings, all within a very close proximity to each other. Use the University of California, Berkeley Campus as a mod..

  The goal of this problem is to simulate a geometric random

The goal of this problem is to simulate a geometric random variable (which will be covered on Friday, Feb 6th in lecture). We will break this problem into two parts.

  Identify the communication protocols

Identify the communication protocols used in a large hospital organization.

  Section on access controls

Refer to the section on Access Controls. What is the difference between "authorization" and "authentication"? What do we use to perform each of these access control functions? What are the advantages and limitations of the different approaches?

  How cost of box is evaluated in lookup table

Cost of box is determined by looking up value in a lookup table. Shipping cost also is determined by looking up value in a lookup table. Use table at cells H23:J28 with a VLOOKUP function to determine cost of a box.

  Software developments is for developers to analyze

The goal of real world software developments is for developers to analyze, design, program, and test complete applications that solve the needs of the customer. The iLab exercises you have been given will give you practice with the specific programmi..

  Description of the data objects that are managed by the s/w

Such as for server systems, operating systems and software environments. Suggestions: Enterprise x86 Servers with Microsoft Windows 2008 64-bit Operating systems, Multi-Processors, TCP/IP Networking, IIS7 ASP.Net 3.5 web application environment, M..

  Determine the frequency of failure

Collect Experimental Data. Bend the provided 30 paper clips until they fail.

  Design a prototype for a standalone desktop

Design a prototype for a standalone desktop OR mobile/tablet application called EILA

  Mobile technologies in a user-friendly manner

The items need to be easily searchable and of sufficiently high resolution for details to be viewed. They need to be accessible through mobile technologies in a user-friendly manner. The University also wants a way to protect the copyright of the ..

  Determine the standard deviation and variation

Determine the standard deviation and variation, and explain their importance in statistical analysis of a data set.

  Examine the major types of networks and hardware

Examine the major types of networks and hardware available in terms of range, speed, security, reliability, and price. Determine the network that you would implement and the hardware that you would need.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd