Also note: Though not part of this assignment, Exercises 5.14 to 5.35 and Programming Projects 5.1 to 5.30 are excellent problems to study for the upcoming test!
Exercises 5.1 to 5.13
public static boolean isSubstring(String a, String sub, boolean isCaseSensitive)
This method takes two strings, either of which may be null, and a boolean, and returns true if the second string is a substring of the first, where the boolean determines whether or not case matters in the comparison (if isCaseSensitive is true, then case does matter).
Note that you may not use any String methods except charAt() and length().
Also include a method with this signature:
public static void checkIsSubstring()
This method uses your isSubstring() method and should work like this:
Enter two strings: abcdef bcd
"bcd" is a substring of "abcdef"
Try again [y or n]? y
Enter two strings: abcdef BCD
"BCD" is a case-insensitive substring of "abcdef"
Try again [y or n]? y
Enter two strings: abcdef BD
"BD" is not a substring of "abcdef"
Try again [y or n]? n
Goodbye!
Of course, your program should work for any legal input (though your try-again code can assume the user entered either 'y' or 'n').
Remember to exactly match the output!
public static boolean isVowel(char c)
This method takes a char and returns true if it is a vowel (a, e, i, o, or u, upper or lower case), and false otherwise.
Then, write a method with this signature:
public static int vowelCount(String s)
This method takes a possibly-null String and returns the number of vowels (a,e,i,o,or u, without regard to case) in that string.
Note that this method must use your isVowel() method on each character in the string s.
Also include a method with this signature:
public static void checkVowelCount()
This method uses your vowelCount() method and should work like this:
Enter some text on the following lines, followed by a blank line:
Celery
by Ogden Nash
Celery, raw
Develops the jaw,
But celery, stewed,
Is more quietly chewed.
That passage contains 26 vowels.
Note that you should use nextLine() inside a loop of some kind to read the input.
public static void printPrimeFactors(int n)
This method takes a positive integer and prints all the prime factors of n (possibly including n itself), where a factor of n is another term for a divisor and is a number that evenly divides n.
Also include a method with this signature:
public static void checkPrintPrimeFactors()
This method uses your printPrimeFactors() method and should work like this:
Enter a positive integer [or 0 to quit]: 21
The prime factors of 21 are:
3, 7
Enter a positive integer [or 0 to quit]: 9
The prime factors of 9 are:
3
Enter a positive integer [or 0 to quit]: 0
Goodbye!
Note that the lines starting with a "3" were printed by the printPrimeFactors() method, and the others by the checkPrintPrimeFactors() method.
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.
Also include a method with this signature:
public static void checkFSM()
This method uses your accepts() method and should work like this:
Enter an FSM spec: 012300333
Enter an input string (or 'q' to quit): 01
The machine ACCEPTS the string 01.
Enter an input string (or 'q' to quit): 110
The machine DOES NOT ACCEPT the string 110.
Enter an input string (or 'q' to quit): q
Goodbye!
public static String toBinary(int n, int bits)
This method takes a non-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.
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.
Also include a method with this signature:
public static void checkToBinary()
This method uses your isBinary() method and should work like this:
Enter a non-negative integer [or <0 to quit]: 5
Enter a minimum number of bits: 6
5 in 6-bit binary equals 000101
Enter a non-negative integer [or <0 to quit]: 5
Enter a minimum number of bits: 2
5 in 2-bit binary equals 101
Enter a non-negative integer [or <0 to quit]: -1
Goodbye!
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.
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.
Also, write the usual check method with a reasonable UI:
public static void checkPrintLanguage()