Trabalho escrito algebra a

Preliminares
1)
B ::=
1 3 = B ÷ C
B2 ::= not A ≤ B + 9
B3 ::= B false
1 ⋀
B4 ::= 3 × A = true
B5 ::= not 4 + C = 4 ⋀ false
S1 ::= skip ; V := 0
S2 ::= if B4 then { skip }
S3 ::= B := 99 ÷ A
S4 ::= 3 × C ; A
S5 ::= if A ≤ B ⋀ A = C then { skip ; 6 × A }
2)
Programas são sentenças e cada sentença usa um construtor. Há quatro tipos possíveis para uma sentença Sexp :
1. Sexp ::= x := Zexp
2. Sexp ::= skip
Nos dois primeiros casos há apenas o uso de um construtor ( " := " e "skip" ).
3. Sexp ::= Sexp ; Sexp
Nesse caso há o uso do construtor "; " que “chama” duas sentenças Sexp. Cada sentença “chamada” pode ter um ou mais construtores, portanto, uma sentença com o construtor "; " possui no total mais de um construtor.
4. Sexp ::= if Bexp then { Sexp }
Há o uso do construtor if then que avalia uma expressão booleana Bexp e em seguida chama uma sentença . Essa sentença pode ter um ou mais construtores. Sexp Portanto, uma sentença com o construtor if then possui no total mais de um construtor.
Propriedades Sintáticas
1)
Pela sintaxe temos quatro possíveis tipos de programas, e o único que faz uso de uma expressão Booleana num programa é o quarto caso: if Bexp then { Sexp }
Logo a única maneira de se ter uma expressão Booleana num programa é quando o mesmo aparece no quarto caso.
2)
Vamos denotar P(n) como o numero de operadores n do programa P.
Passo base:
Para P(1) onde 1 é o numero de operações de um programa , temos :
Sexp 1 if then { } ::= Bexp Sexp
Logo, o número de ‘{‘ = 1 = número de ′if′ = numero de ‘}’ . ou S não tem ‘{‘ nem ‘if’ nem ‘}’:
Sexp 2 := x = S : : exp
Sexp 3 := skip :
Sexp 4 := S ; S : exp exp
Passo Indutivo:
Suponha que para todo N < K, se P(N) possui N operadores, então o número ‘{‘ vai ser igual ao número de if’s e ao número de ‘}’ . Se o programa tiver K>1 operações temos duas opções: Se K tiver uma ou mais operações ( S ::= if Bexp then { Sexp } )
Hipotese:
Se um programa T tiver K > 1