In this project, you will write Java programs to implement recursive definitions
ID: 3745279 • Letter: I
Question
In this project, you will write Java programs to implement recursive definitions of the following languages. Your main() function should read in one command-line value and then indicate with an output of true or false whether or not that value is in the language.
Output should be formatted as shown in the following sample session:
Run
>java TestDivisibleBy7 28
X = 28 Member? true
Turn in source code for all programs, along with the requested output.
1. Language DivisibleBy7 is defined recursively as:
(1) Integer 7 is in DivisibleBy7.
(2) If x is in DivisibleBy7, then so is x + 7.
Encode DivisibleBy7 as a Boolean recursive function. Test your function for input values:
382, 749, 2977, 9989, 52878.
2. Language PowersOf2 is defined recursively as:
(1) Integer 1 is in PowersOf2.
(2) If x is in PowersOf2, then so is 2x.
Encode PowersOf2 as a Boolean recursive function. Test your function for input values:
128, 257, 1023, 8192, 65536.
3. Language SumXY is defined recursively as:
(1) Integers 17 and 43 are in SumXY.
(2) If x and y are in SumXY, then so is x + y.
Encode SumXY as a Boolean recursive function. Test your function for input values:
12, 51, 137, 364, 589.
4. For alphabet {a,b}, the language OddPalindrome is defined recursively as:
(1) Words a and b are in OddPalindrome.
(2) If w is a word in OddPalindrome, then so are awa and bwb (concatenation).
Encode OddPalindrome as a Boolean recursive function. Test your function with input values: abaaba, bbaabbb, abababa, aabcbaa, baabbbaab.
5. For alphabet {a,b}, the language ContainsABA is defined recursively as:
(1) Word aba is in ContainsABA.
(2) If w is a word in ContainsABA, then so are aw, bw, wa, and wb.
Encode ContainsABA as a Boolean recursive function. Test your function with input values:
abaaba, bbaabbb, abbababa, aabbbbaa, baababcab.
6. For alphabet {a,b,+}, the language ABPlus is defined recursively as:
(1) Words a and b are in ABPlus.
(2) If v and w are words in ABPlus, then so are vw and v+w.
Encode ABPlus as a Boolean recursive function. Test your function with input values:
aba+ba, b+ba+bb, ab++ba+a, +aab+bba, b+abb+ab+, a+bbc+bba.
Explanation / Answer
Hi Sir, please find all the Java classes for above mentioned questions:-
1. TestDivisibleBy7.java
public class TestDivisibleBy7 {
public static boolean DivisibleBy7(int num) {
// If number is negative, make it positive
if (num < 0)
return DivisibleBy7(-num);
// Base cases
if (num == 0 || num == 7)
return true;
if (num < 10)
return false;
// Recur for ( num / 10 - 2 * num % 10 )
return DivisibleBy7(num / 10 - 2 * (num - num / 10 * 10));
}
public static void main(String[] args) {
int num = Integer.parseInt(args[0]);
System.out.println("Member? " + DivisibleBy7(num));
}
}
2. TestPowersOf2.java
public class TestPowersOf2 {
public static boolean PowersOf2(int v) {
if (v == 1) {
return true;
} else if (v % 2 != 0 || v == 0) {
return false;
} else {
return PowersOf2(v / 2);
}
}
public static void main(String[] args) {
int num = Integer.parseInt(args[0]);
System.out.println("Member? " + PowersOf2(num));
}
}
3. TestSumXY.java
public class TestSumXY {
public static int SumXY(int x, int y) {
if (y == 0)
return x;
return SumXY(x, y - 1) + 1;
}
public static void main(String[] args) {
int x = Integer.parseInt(args[0]);
int y = Integer.parseInt(args[1]);
int result = SumXY(x,y);
System.out.println("Sum of "+x+" "+y+" is: " + result);
}
}
4. TestOddPalindrome.java
public class TestOddPalindrome {
public static boolean OddPalindrome(String s) {
// if length is 1 then String is palindrome
if (s.length() == 1)
return true;
if (s.charAt(0) == s.charAt(s.length() - 1))
/*
* check for first and last char of String: if they are same then do
* the same thing for a substring with first and last char removed.
* and carry on this until you string completes or condition fails
* Function calling itself: Recursion
*/
return OddPalindrome(s.substring(1, s.length() - 1));
/*
* If program control reaches to this statement it means the String is not palindrome hence return false.
*/
return false;
}
public static void main(String[] args) {
String input = args[0];
if (input.length() % 2 == 0)
System.out.println("Sorry, not a Odd length String");
else
System.out.println("Odd palindrome: " + OddPalindrome(input));
}
}
5. TestContainsABA.java
public class TestContainsABA {
public static boolean ContainsABA(String text, String target) {
// -----------Start below here. To do: approximate lines of code = 4
// 1. base case: null
if (text == null || target == null) {
return false;
} // added target null check
// 2. base case: target too long
if (target.length() > text.length()) {
return false;
}
// 3. base case: same length
if (text.length() == target.length()) {
return text.equals(target);
}
// 4. base case: startsWith OR 5. recursive case
return text.startsWith(target) || ContainsABA(text.substring(1), target);
}
public static void main(String[] args) {
String input = args[0];
boolean result = ContainsABA(input, "aba");
System.out.println(input + " contains aba: " + result);
}
}
Please let me know in case of any clarifications required. Thanks!
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.