2.1 The While Programming Language

Question 1

What is a programming language? What does every language need?

Answer 1

A precise language for giving instructions.

Needs: Syntax: form programs are allowed to take
Semantics: what a program means

Question 2

Define the grammar of while:
S ::==
b ::==
a ::==

Answer 2

S ::== a | skip | S1;S2| if b then S1 else S2 | while b do S | (S)

b ::== true | false | a1 = a2 | a1 ≤ a2 | ¬b | b1 ∧ b2 | (b)

a ::== v | n | a1 + a2 | a1 - a2 | a1 x a2 | (a)

Question 3

how can we extend the while language?

Answer 3

if b then s = if b then s else skip
a1 < a2 = ¬ ( a2 ≤ a1 )
a1 > a2 = ¬ ( a1 ≤ a2 )
a1 != a2 = ¬ (a1 = a2)

Question 4

what does this mean:

⇒

Answer 4

We execute program S in state σ to give a new program S’ and state σ’

Question 5

Give state modification notation

Answer 5

σ[x↦2]

Question 6

are these states:
[x↦y]
[x+ y ↦2]

Answer 6

No