Computer Science Assignment - Desklib

Running head: COMPUTER SCIENCE ASSIGNMENT
COMPUTER SCIENCE ASSIGNMENT
Name of the Student
Name of the Organization
Author Note

1COMPUTER SCIENCE ASSIGNMENT
Answer (1)
Axiomatic semantics I
a = 2 * (3 * b - a)
b = 3 * a -1 {b>17}
3 * a - 1 > 17
3 * a > 18
a = 2 * (3 * b – a) {a > 6}
6 * b – 2 * a > 6
3 * b – a > 3
b > (3 + a) / 3 (Answer involves a relationship between a and b)
It is started by deciding what variable or variables are to be mentioned in the precondition. The
rule for sequences are recalled: the precondition for a statement in a sequence is equal to the
post-condition for the statement that precedes it.
Answer (2)
Axiomatic semantics II

2COMPUTER SCIENCE ASSIGNMENT
Computation of the strongest precondition for the following statements and the given post
condition
if (x > y) then y = 2 * x - 1 else y = 3 * x + 1; { y > 7 }
Wp(if x>y then y:= 2 * x - 1 else y:= 3 * x + 1, (y > 7))
≡ ((x > y)=>Wp(y:= 2 * x - 1 ,(y > 7)) ∧ (¬(x > y)∧Wp(y:= 3 * x + 1,(y > 7))
≡ ((x > y)=>( y:=2 * x - 1 > 7)) ∧ (¬(x > y)=>(y:= 3 * x + 1 > 7))
≡ ((x > y)=> False) ∧ ((x <y)=> True)
≡ (x < y)
The two cases are clearly analyzed that is created by the if-then-else statement: one where x is
greater than y and one where it is not. The weakest preconditions for each are figured out and the
strongest single precondition is evaluated that logically implies both.
Answer (3)
 An input number starts with a + or - sign.
Regular Expression
(+ | -)(1|2|3|4|5|6|7|8|9)*
Regular Grammar
S-> +A |-A
A->1A|2A|3A|4A|5A|6A|7A|8A|9A|1|2|3|4|5|6|7|8|9
 An octal number starts with a 0 and can continue with an arbitrarily number of digits. An
octal number started with more than one 0 is not an acceptable number.
Regular Expression

3COMPUTER SCIENCE ASSIGNMENT
0(1|2|3|4|5|6|7)*
Regular Grammar
S->0A|ε
A->1A|2A|3A|4A|5A|6A|7A|1|2|3|4|5|6|7
 A decimal number starts with any digit except 0 and can continue with an arbitrarily
number of digits. Note: digits used in a decimal number are between 0 and 9.
Regular Expression
(1|2|3|4|5|6|7|8|9)(0|1|2|3|4|5|6|7|8|9)*
Regular Grammar
S->AB|ε
A->1|2|3|4|5|6|7|8|9
B->1A|2A|3A|4A|5A|6A|7A|8A|9A
 0 is an acceptable number, no matter whether we accept it as a decimal or as an octal
number
Regular Expression
0((1|2|3|4|5|6|7)* + (1|2|3|4|5|6|7|8|9)*)*
Regular Grammar
S->0A|ε
A->1A|2A|3A|4A|5A|6A|7A|1|2|3|4|5|6|7|B
B->1A|2A|3A|4A|5A|6A|7A|8A|9A|1|2|3|4|5|6|7|8|9
Answer (4)
 An input number starts with a + or - sign.