[ Bonus / Optional ]
Note: this problem has an unusually verbose description, but rest assured it is no more difficult than the preceding problems. Finite State Machines play an important role in the theory of computation.
For this problem, we will consider a Finite State Machine. This is a very simple machine that has some states, which are numbered and which we will label with circles, and transitions between states, which are labeled with a character (here, either '0' or '1'). We begin in the start state, and we start reading the characters in a string (which must be made of only 0's and 1's). For each character, we move from the current state to the next state along the appropriate transition of the machine. At the end of the string, we say the machine accepts the string if the machine ends up in an accept state. Here, we will assume that there are no more than 10 states, labeled 0 through 9, with state 0 as the start state, and with only one accept state. For example, consider this machine:
The machine has 4 states (0, 1, 2, and 3, written as q0, q1, q2, q3). Its start state is q0. The double-circled state is the accept state, which in this case also happens to be q0 (though that is not always the case).
Now, let's see this machine in action. If the input string is "01", the machine starts in q0, follows the 0 to q1, then follows the 1 back to q0. Since it ends in the accept state, we say that the machine accepts the string "01"
For another example, let's try "110". Here, the machine starts in q0, and follows 1 to q2, then follows 1 to q3, then follows 0 again to q3. Since it ends in a non-accept state, we say that the machine does not accept the string "110".
Now, for this problem we need to encode a finite state machine (subject to our limitations of 10 states and only one accept state) in a string. We will do this as follows:
character 0: the accept state
character 1: the transition from state 0 on input 0
character 2: the transition from state 0 on input 1
character 3: the transition from state 1 on input 0
character 4: the transition from state 1 on input 1
character 5: the transition from state 2 on input 0
character 6: the transition from state 2 on input 1
...
So, we would encode the machine from above as this string:
"012300333"
To be sure you understand this, here is some explanation
character 0 (underlined here: "012300333"): the accept state is 0
character 1 (underlined here: "012300333"): state 0 on input 0 transitions to state 1
character 2 (underlined here: "012300333"): state 0 on input 1 transitions to state 2
character 3 (underlined here: "012300333"): state 1 on input 0 transitions to state 3
character 4 (underlined here: "012300333"): state 1 on input 1 transitions to state 0
...
Write a method with this signature:
public static int nextState(String machine, int state, char transition)
This method takes a machine description (like "012300333"), a current state (from 0 to 9), and a character (either 0 or 1) indicating which transition to take from the current state. The method returns the new state (an int from 0 to 9) which results from taking the given transition using the given machine specification.
Then, write a method with this signature:
public static boolean accepts(String machine, String input)
This method takes a machine description and an input string (which is guaranteed to be non-null and non-empty and containing only 1's or 0's), and returns true if the machine ends in an accept state when run on the given input string and false otherwise.
Note: this method will call your nextState() method for each character in the given input string.
Here is the start of a test method:
public static void testAccepts() {
assert(accepts("012300333","01") == true);
assert(accepts("012300333","110") == false);
}
[ Bonus / Optional ]
Write a method with this signature:
public static String toBinary(int n, int bits)
This method takes a non-negative integer and a required number of bits and returns a string of at least "bits" length representing that number in binary (base 2), adding leading 0's as necessary. If the number is longer than the given number of bits, it is not truncated but no leading 0's are added. If the first parameter is negative, the method returns null.
Note: while there are other ways to solve this, here you must work as follows:
Start with your result string equal to "".
If n is zero, just set the result to "0". Otherwise, while the number n > 0, extract the rightmost bit of n by taking the number n % 2, and add this on to the appropriate side of the result string, then divide the number n by 2 to shift it in binary one digit to the right. Keep doing this until n is 0.
Finally, add as many leading 0's as necessary.
Here is the start of a test method:
public static void testToBinary() {
assert(toBinary(5,6).equals("000101")); // Convert 5 to 6-bit binary
assert(toBinary(5,2).equals("101")); // Convert 5 to 2-bit binary (requires 3 bits)
assert(toBinary(-5,2) == null);
}
That was just the prelude. Now to the main act. Write a method with this signature:
public static void printLanguage(String machine, int maxDigits)
This method combines your previous two answers as such: it takes an FSM specification and a maximum number of digits. Then it generates every possible input using maxDigits or fewer, and prints out all the input strings that the FSM accepts in that range. To do this, the program runs a counter from 0 to (2maxDigits-1), and converts these values using the toBinary() method from above, then submits those strings to the accept() method from above. It prints out just those strings that are accepted.
Note: this method must print out to both the console and the file out.txt!
Hint: You do not have to compute the upper bound of (2maxDigits-1). Instead, you can just keep increasing your counter forever, but break out of your loop when toBinary() returns a string that is too long.
Finally, write a test method as such:
public static void testPrintLanguage()
Testing this method can be tricky, seeing as it is a "void". But we also save the output to the file "out.txt". So your test method should run printLanguage, read in the file "out.txt", and compare its contents to a known result.
[Bonus / Optional]: Write a program, Hw5BonusGraphics1.java, that draws four graphics at once, each occupying one quadrant of the window, as such:
Note: collectively, the four graphics must fill the entire window, even as the window is being resized by the user (without regard to what happens when the window gets too small to properly render the flags), with each graphic occupying 1/4th of the window. This week you should continue to color-match, rather just using built-in colors.
Also:
you must use "for" loops when appropriate. This includes a separate
"for" loop for each of the following (and perhaps others, too!):
* The diagonal pattern of 7 full and 2 half stars in
Bosnia and Herzegovina's flag (larger
image)
* The 14 red-and-white stripes in Malaysia's flag (larger
image)
* The 13 red-and-white stripes in the US flag (larger
image)
* The pattern of 50 stars in the US flag
* The many-toothed pattern (with 9 white points) in
Qatar's flag (larger
image)
* The makeStar method that is described below (for both
the 5-pointed and 14-pointed stars)
To do this, you will write additional static paint methods, one for each
quadrant of the window, like this:
public static void
paintBosniaAndHerzegovinaFlag(Graphics page, int left, int top, int width,
int height) {
// your code here!
}
public static void paintMalaysiaFlag(Graphics page, int left, int top,
int width, int height) {
// your code here!
}
public static void paintUSFlag(Graphics page, int left, int top, int
width, int height) {
// your code here!
}
public static void paintQatarFlag(Graphics page, int left, int top, int
width, int height) {
// your code here!
}
Note that the "width" and "height" in these signatures represent the
bounding regions for the given flag, and not the width and height of the
entire window! The main paint method will just call these paint
methods, providing appropriate arguments to place the flags in the
appropriate quadrant of the window, so your paint code will look like this:
public void paint(Graphics page) {
int width = getWidth();
int height = getHeight();
paintBosniaAndHerzegovinaFlag(page, 0, 0,
width/2, height/2); // top-left quadrant
paintMalaysiaFlag(....); // you fill
in the parameters
paintUSFlag(....);
// ditto
paintQatarFlag(....);
// ditto
}
Additionally, you must write one more static method that makes an
n-pointed star with exactly this signature:
public static
Polygon makeStar(int nPoints, int cx, int cy, int r1, int r2) {
}
This method will create and return a new Polygon that represents a star with
"nPoints" points, centered at the location (cx,cy), with an outer radius of
"r1" and an inner radius of "r2". You must use this method to create
the 5-pointed stars in Bosnia and Herzegovina's flag and the US flag, and
you must also use this same method to create the 14-pointed star in
Malaysia's flag.
Note: Do not use the Polygon.translate method this time -- instead,
make repeated calls to makeStar, one for each star in each flag.
[Bonus / Optional]: Write a program, Hw5BonusGraphics2.java, as such:
First, write a method that takes a page, a color, a center point (cx,cy), and a radius, and -- using the technique we covered in class -- draws a single astroid (the type of hypocycloid in the Steelers logo) in the given color that is just contained by the circle with the given center and radius. Here is a picture of an astroid drawn in this manner, with about 10 points on each positive or negative coordinate axis:
Next, write a method that takes a page, a center point (cx,cy), and a radius, and -- using your astroid-drawing method -- draws a Steelers logo just contained by the circle with the given center and radius. Here is a picture of a Steelers logo:
Note that you do not have to exactly color match (use built-in colors), and you do not have to exactly match the font (but you should use a bold font, at least), and you do not have to exactly place the "Steelers" string (do an ok job, but we have not learned how to center or otherwise accurately place strings, so "close" is close enough for this problem). This assignment is about methods, loops, and conditionals, and not about strings, so do not spend too much time perfecting how the string looks!
Finally, use this Steelers-logo-drawing method as follows:
- In the bottom-left quadrant of the window:
Draw a single Steelers logo, centered in the quadrant, as large as the smaller of the quadrant's width and height (so the logo just fits into the smaller of the two dimensions of the quadrant). If the quadrant is too small to draw a reasonable Steelers logo, just draw a single green astroid centered in the quadrant.
- In the top-right quadrant of the window:
Draw a 3-by-3 "checkerboard of Steelers logos", where the Steelers logos replace the red squares in a standard red-and-black checkerboard (again, with the red square -- now the Steelers logo -- in the top left). If the quadrant is too small to draw this many reasonable Steelers logos, each of them should be replaced with a single green astroid of the same size. Don't worry if the quadrant gets too small to even see these green astroids.