Home
Syllabus
Assignments
Tests
printable version
| S | → | λ | a S b S | b S a S |
| S | ⇒ | aSbS |
| ⇒ | aaSbSbS | |
| ⇒ | aabSbS | |
| ⇒ | aabbS | |
| ⇒ | aabbaSbS | |
| ⇒ | aabbabS | |
| ⇒ | aabbab |
| S | → | z | A + S |
| A | → | x | y A |
|
|
| S | → | T + S | T |
| T | → | F T | F |
| F | → | x | y | ( S ) |
Draw a syntax tree for the sentence x ( x + y ).
| S | → | V V | V |
| V | → | ( S ) | x | y | z |
a. x ( y )
b. x y z
c. x ( y z )
| a. | x ( y ) |
It is described by the grammar. |
| b. | x y z | It is not described by the grammar |
| c. | x ( y z ) |
It is described by the grammar. |
Write a context-free grammar describing each of the following languages.
| a. | the set of strings of a's and b's beginning and ending with the letter a |
| b. | the set of strings containing either only a's or only b's |
| a. |
| |||||||||
| b. |
|
Write a context-free grammar describing each of the following languages.
| a. | the set of strings containing only a's and b's consisting entirely of repetitions of the same letter, except the final letter, which must be different. Examples include aaaab, bbbbbba, and ab. |
| b. | the set of strings containing a's, b's, and c's where no a's appear after the first b |
| a. |
S → a X | b Y
X → a X | b Y → b Y | a |
| b. |
S → X Y
X → a X | c X | λ Y → b Y | c Y | λ |
Write a context-free grammar describing the set of strings containing only a's and b's with at least one a and at least one b.
| S | → | T a T b T | T b T a T |
| T | → | a T | b T | λ |
The below program will execute, but it does not work as intended. Suppose the user executes the program, entering 77 when prompted. What does the program display?
public class Mystery {
private int x;
private int y;
public void run() {
x = readInt("Query? ");
y = help(x);
println(y + " divides " + x);
}
public int help(int n) {
for(int i = 2; i * i <= n; i++) {
x = n % i;
if(x == 0) return i;
}
return n;
}
}
What is the purpose of a constructor?
Its purpose is to initialize the instance variables of a newly allocated object.
Write an Account class for tracking the balance of a bank
account. The class should include a double variable named
balance for remembering the current balance, and it
should have the following constructor and method.
Account(double init)(Constructor)
Constructs a bank account whose current balance is
init.
double deposit(double value)Increases this account's value by value, returning
the new balance.
The following fragment illustrates how a
program might use the Account class.
Account acct = new Account(10.00); println(acct.deposit(5.00)); // displays 15.0 println(acct.deposit(3.00)); // displays 18.0
class Account {
private double balance;
public Account(double init) {
balance = init;
}
public double deposit(double value) {
balance += value;
return balance;
}
}
Write a Student class for tracking a
student's grades in CSCI 150.
The class includes two int instance variables: one named
total tracks how many points the student has earned thus
far, and another named possible tracks how many possible
points the student could have earned thus far.
The class includes one constructor and two methods.
Student()(Constructor) Constructs a student who has had completed no graded work for the class.
void register(int value, int poss)Registers that this student has completed work with a grade of
value out of a possible poss.
double getPercent()Returns the percent of possible points thus far earned. (The method returns 100.0 when no graded work has been completed.)
The following fragment illustrates how a
program might use the Student class.
Student robin = new Student(); println(robin.getPercent()); // displays 100.0 robin.register(20, 30); robin.register(10, 20); println(robin.getPercent()); // displays 60.0
class Student {
private double total;
private double possible;
public Student() {
total = 0.0;
possible = 0.0;
}
public void register(int value, int poss) {
total += value;
possible += poss;
}
public double getPercent() {
if(possible == 0.0) {
return 100.0;
} else {
return 100 * total / possible;
}
}
}
Write a class ScoreCard providing the following constructor
and methods.
ScoreCard(int par)(Constructor) Constructs a score card for tallying scores, where
par is the goal for each score.
void add(int score)Adds a score onto this score card. (The easiest way to solve this problem is not to remember each individual score added into the card; however, you may approach the problem that way if you wish.)
int getBirdieCount()Returns the number of values added into this score card that are
below par.
int getParDifference()Returns the sum over all scores of the difference between the score and the goal. For example, if the goal is 3, and the scores added are 2 and 5, then the method returns 1, since that is the sum of 2 − 3 and 5 − 3.
class ScoreCard {
private int goal;
private int birdies;
private int parDiff;
public ScoreCard(int par) {
goal = par;
birdies = 0;
parDiff = 0;
}
public void add(int score) {
if(score < goal) birdies++;
parDiff += score - goal;
}
public int getBirdieCount() {
return birdies;
}
public int getParDifference() {
return parDiff;
}
}