What is the alphabet in the automata associated with this planet?
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
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).](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fd99806c6-42e8-450c-a219-a2d748677dac%2Fe40e7de7-ab0a-487d-bece-5c9ad3293e23%2Fdlgv71g_processed.png&w=3840&q=75)
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
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 2 images
Knowledge Booster
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
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
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)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education