Theory of Computation

This article covers various topics related to Theory of Computation, including transitive relation, first-order logic, and regular expressions. It includes solved assignments and essays, and provides expert guidance on these topics.

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)

Theory of Computation 5
Question three
Consider an instantiation of first-order logic with an equality relation ≡ and a binary relation:
contains (x, y) meaning x is contained within y.
(a) [2 marks] Write a formula in first-order logic that captures the idea of their existing an entity
which contains all other entities, but not itself.
Consider the following two propositions:
∀x, y, z. contains (x, y) ∧ contains (y, z) → contains (x, z) (1)
∀x, y. ¬ (x ≡ y) → (contains (x, y) ∨ contains (y, x)) (2)
Proposition (1) describes that contains is a transitive relation.
The formula is: Vx’(x=y)^contains (x,y).
This means that x is not equivalent to y and y contains all x which are not equivalent to it.
(b) [2 mark] Describe (in natural language terms) the property defined by proposition (2).
The contains I this proposition means that the equation is a symmetric since the equations is
inversely equal from all sides.
(c) [4 marks] Give a concrete universe U with four elements and a definition of contains which
satisfies the above two properties (1) and (2).
The four elements are the De Morgan’s law, the quantifiers law, the negation law and the
associative law.
(d) [4 marks] Prove the following sequent is valid: ∀x.∀y. contains (x, y) ∨ contains (y, x) ` ∃z.
contains (z, z)
The following proposition captures a property that for any two entities where one is contained in
the other, then these are distinct elements:
∀x. ∀y. contains (x, y) → ¬ (x ≡ y)
An alternate way of stating this property is that an entity cannot be contained in itself:
∀x.¬ contains (x, x)

Theory of Computation 6
These are two equivalent ways of stating irreflexively for contains.
Given the expressions
Vx,y,z contains (x,y) A contains (y,z)-> contains (x,x) and
Vx, y ‘(x=y) -> contains (x,y) V contains (y,x ).
The transitive proposition can give
Vx,yz=(x,y) ^ (y,z)^(x,z)
Vxyz=xy, yz^ xz
Vxyz=xy,yz^xz
Therefore Vx,yz=xy(x,z-<y)
(e) [8 marks] Prove the following sequent valid:
∀z. z ≡ z, ∀x. ∀y. contains (x, y) → ¬ (x ≡ y) ` ∀x.¬ contains (x, x)
i.e., you are proving one direction of the equivalence between the two definitions of irreflexively
(assuming also that equality ≡ is reflexive).
From Vz.z
From Vz.z=z Vx.Vy=(x,y) x=y Vx(x,x)
Z’=Vx.Xy=x2,y2Vx(x2)
^Z’=RI2 +Inx2^y=y2^z0=z’0
It follows that
nZ1’=Z1’

Theory of Computation 7
Question four
The formal languages of logical expressions in various Logics are generally not regular.
However, conjunctive normal forms can be described as a regular language. The reason this is
possible is that we do not need nested parentheses to express CNFs, one level of parentheses is
sufficient. To avoid confusion with the grouping characters for regular expression we write L
instead of the opening parenthesis, and R instead of the closing parenthesis.
To express different propositional variables, we write different non-empty sequences of the letter
A.
So, our alphabet for this is {A, L, R, ∧, ∨, ¬}. For example, the CNF X ∧ (¬X ∨¬Z)∧(Y ∨Z)
could be expressed as A∧L¬A∨¬AAAR∧LAA∨AAAR, with A standing in for X, AA for Y
and AAA for Z.
1. Write the following series of regular language definitions over the alphabet mentioned above.
The later definitions can use the names of the earlier definitions, e.g. in the definition of CNF
you can use CLAUSE and LITERAL, you do not have to replace them by their definitions.
When given the CNF example
X^ (‘xVyz) ^( y’z) over the alphabet
{A,L,R^;Z}
This will give A^L’Av;AAAR ^ LAAvAAAR
X-A
Y-AA
Z-AAA
(a) [4 marks] Give a regular expression for the language of literals, based on the above
conventions. For example, AA and ¬AAA are literals.
When given literals
AA, ‘AAA
Y, ‘z
(y) (‘z)
(b) [4 marks] Give a regular expression for the language of clauses. Examples of clauses: A, A ∨
¬A, AA ∨ A ∨ ¬AAA.
When given the clause
A,Av’A, AAvAV,’AAA
(x),(xV’x),(yVxv’z)
(x), (1), (x’y’V’z)
(c) [4 marks] Give a regular expression for the language of conjunctive normal forms. Examples
of CNF: A, LA ∨ ¬AAR ∧ ¬AAA, LA ∨ AR ∧ LAA ∨ ¬AAAR ∧ ¬A.
When give the example of CNF

Theory of Computation 8
A, LAV ^AARA^AARA^AAA, LA ^VAAR^LAA^AAARA^A
Next x, (x^yz) ^z, (x^y)^,(xVz)
^(yV’z),^’x
x, (x^yz) ^z, (x^y)^,(xVz)
^(yV’z),^’z
X, (x^yz)v (‘y^’z),(x^’z)v (y^’z)
(yv’z)
Finally (x), ‘z^ (x’y) (x^y)^’z (yv’z)
2. [8 marks] The DPLL algorithm does something boring (case-split) when it can cannot do
anything clever, such as remove tautologies, propagate unit clauses, or remove clauses with pure
literals. But can we leave the detection whether we can do something clever to a finite
automaton, in any of the cases? Technically, this boils down to answering the following
questions:
(a) Is the language of CNFs that contain a tautological clause regular?
Yes, if the clause has both the literal and the negation factor.
(b) Is the language of CNFs that contain a pure literal regular?
It is only regular if it is a conjunction resulting from more than once clause
(c) Is the language of CNFs that contain a unit clause regular?
It is termed as regular if it contains only a single literal.

Theory of Computation 9
Justify your answers with explanations.
Link[new]=top
Top=new
Struct node {
Int age;
Struct node*next;
}
Top=null;
Struct node*new;
Move=(struct node) mal(size of struct node);
New->age=item;
New =next=top;
Top=new
Struct node* prt
Ptr=top;
While ptr=null{
Printl(“%d”,ptr->age);
Ptr=next->ptr;
Stack with linked list
Top=null, write underflow
Item=into[top];
Temp=top
Top=link[top]
Link[temp]=avail
Avail=temp

Theory of Computation 10
Question five
In this section your task is to translate/transform a regular expression into an NFA, and then
remove the -transitions of the NFA whilst preserving the language. The regular expression in
question is the following:
−?(0 | 1)(0 | 1)∗ .(0 | 1)∗ (e−?(0 | 1)(0 | 1)∗ )?
The motivation are similar regular expressions describing floating point constants in
programming languages, except that we restrict this to binary digits to keep things simple. The
“?” in this expression is a shorthand for optional expressions, that is R? is equivalent to R | .
1. [4 marks] What is the alphabet of this regular expression?
The alphabet is a finite set of symbols, 0 and 1.
2. [8 marks] Translate the expression into an NFA, using the techniques from the lectures. If you
use the “generally unsafe” translation of R∗ explain why it is in this particular context safe.
0,1
e
e
e 0,1 0,1
3. [6 marks] Now create an equivalent NFA without -transitions, again using the techniques from
the lecture.
0,1 0,1
0,1
0,1
4. [2 marks] Is the NFA you have produced in the previous step already a DFA?
Justify your answer.
Yes. The final state of the logic has the series ending at the same location.
A B C D E
F G
A B C D E
GHF

Theory of Computation 11
References
Bibliography
Nfa, R.W. and Welch, R., 2010. Changing States: Transformations in Modern Irish Writing. Routledge.
Youssef, N.F., Shepherd, A., Evans, J.M. and Wyke, S., 2012. Translating and testing the L iver D isease
S ymptom I ndex 2.0 for administration to people with liver cirrhosis in E gypt. International journal of
nursing practice, 18(4), pp.406-416.