U08025: Translate the following into proper Propositional Logic sentences: Foundations of Computation Coursework, OBU, Singapore

ASSIGNMENT QUESTION (100%)

QUESTION 1

a. Translate the following into proper Propositional Logic sentences.

“John or Jenny steal the book. Jenny does not steal the book if she is honorable. Jenny is honorable if she always tells the truth. Jenny always tells truth.”

Prove that “John steals the book” is a logical consequence of the above using Resolution with Reductio Ad Absurdum (RAA).

b. Consider the following rules and facts.

R1: sheriff(X) ∧ jurisdiction(X,Y) → peace_officer(X,Y)
R2:deputy(X) ∧ jurisdiction(X,Y) → peace_officer(X,Y)
R3:safety-officer(X) ∧ jurisdiction(X,Y) ∧ appointed(X, Y) → peace_officer(X,Y)
R4:sheriff(john)
R5:deputy(paul)
R6:safety-officer(pete)
R7:jurisdiction(john, london)
R8:jurisdiction(paul, oxford)
R9:jurisdiction(Pete, manchester)
R10: appointed(Pete, manchester)

Note: A term that starts with a capital letter is a variable.

(i). Find all solutions for peace_officer(X,Y) using resolution principle with Reductio Ad Absurdum (RAA). Draw the full resolution proof tree

(ii)Translate the clauses into the Prolog program. Test the program https://swish.swi-prolog.org/.

QUESTION 2

a. Draw the transition diagram for a DFA, with the alphabet {a, b, c}, that accepts the following language: Explain how the DFA accepts strings in L

b. Draw the transition diagram for a DFA, with the alphabet {a, b, c}, that accepts the following language: Explain how the DFA accepts strings in L

c. Combine the two DFAs in (a) and (b) to produce a diagram for NDFA, with the alphabet {a, b, c}, that accepts. Explain how the NDFA accepts strings in

d. Using subset construction, convert the NDFA in (c) to an equivalent DFA and draw the transition diagram. Explain how the DFA accepts strings in

e. Using product construction, combine the two DFAs in (a) and (b) to produce a diagram for the DFA that accepts. Explain how the DFA accepts strings in

f. Write the regular expressions for the following languages: L₁, L, and.

g. write the regular grammars for the following languages: L₁, L, and.

i. Draw an NDFA that accepts the language generated by grammar, where the set of non-terminals, the set of terminals, S is the initial symbol and is the set of 3 production rules as shown below.

S → aX | bY
X→ bX | aY | bY | λ
Y→ bY | bS | aX | aY

QUESTION 3     

a. Draw the transition diagram of a pushdown automaton (PDA) that accepts the following language.

Show the executions of the PDA for the following strings:  and

b. Write down a context-free grammar (CFG) that generates. Give the derivations of the CFG for the following string: