Theory of Computation

Running head: Theory of Computation 1
Theory of Computation
Student name
Institution
Location of Institution
Date

Theory of Computation 2
Question one
(a) [2 marks] What are the possible values of p, q, and r in the event of "Path B" is printed to
console?
The values are;
p=true;
q=true;
r=false;
(b) [8 marks] Give a natural deduction proof that "Path C" can never be printed. This will require
you to model, as a proposition, the state of the variables p, q, and r in the event of line 13.
This is for the main if statement: p || q -> False -> Else section => p=false and q=false
This is for the inside if statement: p && r->True (For path c) => p = true and r=true
This cannot happen as this is a contradiction where p cannot be true and false at the same time.

Theory of Computation 3
Question two
Consider the following finite-state automata:
start
We will model the current state of the automata by atoms, a, b, and c, and the next state of the
automata by atoms a0, b0 and c0. The transition relation and start state are modelled by the
propositional formulas:
transition = (a → (¬a 0 ∧ b 0 ∧ ¬c 0)) ∧ (b → (¬a 0 ∧ ¬b 0 ∧ c 0))
start = a ∧ ¬b ∧ ¬c.
Together these two propositions provide the model we will use: model =transition ∧ start We
can model a specification that the state c is not accessible after one step of the automata by:
specification = ¬c 0
(a) [5 marks] Convert the proposition ¬ (model → specification) into Conjunctive Normal Form
(CNF) via a sequence of equational reasoning steps. Label each step with the axiom applied in
that step.
Transition (a(‘a0 ‘b0 ‘c0))^(b->(‘a0’b0’c0))
Start ‘a’b’c
Model=transition ^start
Apllying domorgan’s law
(a’a0Vab0Cac0)
Logic equuivalance a’a0^ab’0^a’c0 b’a0
Double negation (‘a’a0^ab0^ac0’b’c0)
Associative law (‘a’b’c) a(a^b^0) b(a^0)
Distributive law (‘a’c)^(b’c)^(a’0)
Negation law (a’c)(b^c)(a^0)
Identity law (a^b^c)
a b c

Theory of Computation 4
(b) [5 marks] Apply DPLL to your answer to the previous question. Comment on whether your
result shows if model → specification is valid.
From the above, we can check the validity
A^b^c to show mode->specification
We include the backtracking + unit propagation pure literal rule
We say:
The formula F can be satisfied by:
F+ (a1=true) or F+(b1=true) or F=(c1=true)