Homework Help is Here – Start Your Trial Now!
Engineering
Computer Science
What is the alphabet in the automata associated with this planet?

What is the alphabet in the automata associated with this planet?

Database System Concepts
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
See similar textbooks
icon
Related questions
Question
1. StrangeNEWS® just reported that suddenly a very VERY strange planet appeared out of nowhere! Three species, A, B and C are living on this planet. Any two different species can mate. If they do, two children will be born and they themselves will die. The planet will fail if there only one kind of specie left (therefore, no more mating can take place). We denote mating between two individuals from B and C species by a. Similarly, we define b and c. We want to draw an automaton for any given initial number of species on the planet that tells us whether a sequence of mating is possible and/or causes the planet to fail. For example, let's say there is only one individual of species A and one of species B. Then, the only way that a mating can happens is if these two individual mate with each other (mating of type c). We can draw a finite automaton for it as below: 110 As you can see, final state in this automoton is when the planet failes (not more mating possible or, in other words, there are only individuals from one species left on the planet). Moreover, we labelled each state by ryz where x,y and z are respectively the number of individuals of species A, B and C. If one of the numbers is larger than 9, then we can use commas, like 3, 2, 10, to label a state. If we wanted to draw all transitions, the (complete) transition graph would have been as this: 110 CSc 135 с D с C 6 b T 002 Answer the following questions about this strange planet and the automata associated with it. (a) [4 points] What is the alphabet Σ in the automata associated with this planet? Page 1 of 5 002 Homework Assignment 2 (b) [4 points] Describe the rule(s) that specifies whether a string belongs to the language. (c) [5 points] Any DFA can be modified so that we have at most one trap state (by easily modifying the original DFA such that any transition leading to a trap state leads to a single particular trap state). Write the transition matrix of the automaton above (the one with the trap state).
Transcribed Image Text:1. StrangeNEWS® just reported that suddenly a very VERY strange planet appeared out of nowhere! Three species, A, B and C are living on this planet. Any two different species can mate. If they do, two children will be born and they themselves will die. The planet will fail if there only one kind of specie left (therefore, no more mating can take place). We denote mating between two individuals from B and C species by a. Similarly, we define b and c. We want to draw an automaton for any given initial number of species on the planet that tells us whether a sequence of mating is possible and/or causes the planet to fail. For example, let's say there is only one individual of species A and one of species B. Then, the only way that a mating can happens is if these two individual mate with each other (mating of type c). We can draw a finite automaton for it as below: 110 As you can see, final state in this automoton is when the planet failes (not more mating possible or, in other words, there are only individuals from one species left on the planet). Moreover, we labelled each state by ryz where x,y and z are respectively the number of individuals of species A, B and C. If one of the numbers is larger than 9, then we can use commas, like 3, 2, 10, to label a state. If we wanted to draw all transitions, the (complete) transition graph would have been as this: 110 CSc 135 с D с C 6 b T 002 Answer the following questions about this strange planet and the automata associated with it. (a) [4 points] What is the alphabet Σ in the automata associated with this planet? Page 1 of 5 002 Homework Assignment 2 (b) [4 points] Describe the rule(s) that specifies whether a string belongs to the language. (c) [5 points] Any DFA can be modified so that we have at most one trap state (by easily modifying the original DFA such that any transition leading to a trap state leads to a single particular trap state). Write the transition matrix of the automaton above (the one with the trap state).
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 4 steps with 2 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Knowledge Booster
Problems on Turing Machines
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.
Recommended textbooks for you
Database System Concepts
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education
SEE MORE TEXTBOOKS