Hey I need some java help. Im doing book problems and am having trouble with the
ID: 3600659 • Letter: H
Question
Hey I need some java help. Im doing book problems and am having trouble with these two! All help is greatly appreciated!
1. Write a recursive recognizer program for the language L who’s syntax is given by the following grammar:
L -> A<L>A | B<L>B | C
Sample strings in the language are
AACAA BBCBB C ABCBA AABCBAA
The header for this method MUST be:
public boolean isValidProblem1( String word)
2. Write a recursive recognizer program for the language L where sentences (S) in the language are of the format:
L = { S: S is of the form A2nBn} Thus a sentence is in L if it consists of a sequence of A’s followed by a sequence of half as many B’s AAAABB is valid but AAABB and ABABAB is not
The header for this method MUST be:
public boolean isValidProblem2( String word)
Explanation / Answer
Full program
class Main{
public boolean isValidProblem1( String word)
{
// string is of odd length and it is base case
if(word.length() == 1)
{
if(word.charAt(0) == 'C')
return true;
return false;
}
// string is of even length which should be rejected
else if(word.length() == 2)
return false;
// comparing first and last characters
// recursively calling function taking substring removing first and last characters
else{
if(word.charAt(0) == word.charAt(word.length()-1))
return isValidProblem1(word.substring(1,word.length()-1));
else
return false;
}
}
public static void main(String[] args)
{
Main a = new Main();
System.out.println(a.isValidProblem1("AACAA"));
System.out.println(a.isValidProblem1("BBCBB"));
System.out.println(a.isValidProblem1("C"));
System.out.println(a.isValidProblem1("ABCBA"));
System.out.println(a.isValidProblem1("AABCBAA"));
System.out.println(a.isValidProblem1("ABBCBAA"));
}
}
/*SAMPLE OUTPUT
true
true
true
true
true
false
*/
{
// string is of odd length and it is base case
if(word.length() == 1)
{
if(word.charAt(0) == 'C')
return true;
return false;
}
// string is of even length which should be rejected
else if(word.length() == 2)
return false;
// comparing first and last characters
// recursively calling function taking substring removing first and last characters
else{
if(word.charAt(0) == word.charAt(word.length()-1))
return isValidProblem1(word.substring(1,word.length()-1));
else
return false;
}
}