Logic Programming + Finite State Machines

Question 1

What are the 5 data objects/terms

Answer 1

-Numbers
-Atoms
-Variables
-Compound terms
-Lists

Question 2

What is a number

Answer 2

A number may be either an integer or a floating point
quantity (e.g 42 or -816.22)

Question 3

What is an atom

Answer 3

An atom is a constant that does not have a numerical value. It
begins with a lowercase letter, or is quoted (e.g buffalo or ‘The X Files’)

Question 4

What is a variable

Answer 4

A variable stands for a term that is to be determined. It begins
with an uppercase letter or ‘_’ (e.g X or Person_A)

Question 5

What is a compound term

Answer 5

A compound term consists of a functor followed by a
sequence argument terms in brackets (e.g dog(rover))

Question 6

What is a list

Answer 6

A list is a structured data type made up of a sequence of terms
enclosed in square brackets and separated by commas (e.g [dog, X, 220, 500])

Question 7

What could a clause be

Answer 7

A clause may be
-a fact
-a rule

Question 8

What is a fact

Answer 8

A fact is taken to be true. It must be an atom or a compound term and end in a full stop (e.g christmas. or dog(fido).)

Question 9

What is a rule

Answer 9

A rule may be either true or false — only computation will
show. It must be an atom or a compound term, followed by a
“:-” followed by further atoms or a compound terms,
separated by commas (e.g grandfather(X, Y) :- father(X, Z), parent(Z, Y).)

Question 10

What is the declarative reading of h :- t1, t2, … tk

Answer 10

h is true if t1, t2, … tk are all true

Question 11

What is the procedural reading of h :- t1, t2, … tk

Answer 11

To compute h, compute t1, t2, … tk

Question 12

What is a predicate

Answer 12

A predicate is defined by several clauses

Question 13

What is a list

Answer 13

A list is made up of elements (possibly of different type)
enclosed in square brackets and separated by commas

Question 14

What is the Cons Notation

Answer 14

The “cons” (or “|”) notation allows one to represent a list as
being constructed from some leading elements and a list (e.g [1, 2, 3 | [4, 5]] = [1, 2, 3, 4, 5])

Question 15

sum_list( [], 0 ).
sum_list( [H|T], R )
:- sum_list( T, W ),
R is H + W.
In this predicate, what does H and T stand for

Answer 15

H is the head of the list, and T is the Tail

Question 16

What is the member predicate

Answer 16

The member predicate is true when an element is a member of a list
member_list( E, [E|] ).
member_list( E, [|T] )
:- member_list( E, T ).

Question 17

What is the append predicate

Answer 17

An append predicate appends two lists
append_list( [], Y, Y ).
append_list( [H|T], Y, [H|W] )
:- append_list( T, Y, W ).

Question 18

What is the reverse predicate

Answer 18

A reverse predicate reverses a list
reverse_list( [], [] ).
reverse_list( [H|T], R )
:- reverse_list( T, W ),
append( W, [H], R ).

Question 19

How can an atom be viewed as a list of ASCII codes

Answer 19

The “name” predicate allows one to convert from an atom to a list of integers
name( ace, X ).
X = [ 97, 99, 101 ]

Question 20

Not really anything but just an example of making characters uppercase idk it might be useful

Answer 20

make_upper( [], [] ).
make_upper( [H|T], [V|W] )
:- to_upper( H, V ),
make_upper( T, W ).

to_upper( A, B )
:- B is A - 32.

Question 21

What is the infix operator to carry out arithmetic

Answer 21

The operator ‘is’

Question 22

What happens if the left argument of the arithmetic is an unbound variable

Answer 22

Bind it to the result of evaluating evaluating the right argument, and succeed

Question 23

What happens if the left argument is a number, or a bound variable with a numerical values

Answer 23

Succeed if the right argument has the same numerical value

Question 24

What are the arithmetic operators

Answer 24

X + Y: sum of X and Y
X - Y: difference of X and Y
X * Y: product of X and Y
X / Y: quotient of X and Y
X // Y: integer quotient of X and Y
X mod Y: remainder when X is divided by Y
X ^ Y: value of X to the power Y

Question 25

What are the arithmetic functions

Answer 25

abs( N, X ): absolute value of N
sin( N, X ): sine of N (in radians)
cos( N, X ): cosine of N (in radians)
log( N, X ): natural logarithm of N
sqrt( N, X ): square root of X

Question 26

What are the relational operators

Answer 26

X =:= Y: X and Y are same value
X == Y: X and Y are not same value
X > Y: X greater than Y
X >= Y: X greater than or equal to Y
X < Y: X less than Y
X =< Y: X less than or equal to Y

Question 27

What are the unification operators

Answer 27

X = Y: X and Y can be unified
X = Y: X and Y cannot be unified
(ok so its supposed to be a backslash for the bottom one but its not appearing)

Question 28

What is the only logical negation operator

Answer 28

+ X not X
(backslash isnt working here either)

Question 29

What is the closed-word assumption

Answer 29

What is stated is true; what is not stated is false

Question 30

What does ‘negation as failure’ mean

Answer 30

Anything that cannot be
proved true is false.

Question 31

How do you construct ‘if-then-else’

Answer 31

By using -> ; (e.g maxof( X, Y, Z )
:- ( X =< Y
-> Z = Y
; Z = X
). )

Question 32

How does Prolog attempt to satisfy a sequence of goals

Answer 32

It system attempts to
satisfy each goal in turn, working from left to right. If all the goals succeed in turn, the sequence of goals succeeds
as a whole.

Question 33

A goal must be a call term, what is a call term

Answer 33

Either an atom, a compound
term, or an “is”, but not a number.

Question 34

How does the Prolog system work to satisfy a single goal

Answer 34

It works through the
clauses in the database from top to bottom, examining those
clauses that have a functor and arity that unify with the goal.
(A functor is the atom part of a compound term and arity is the number of arguments)

Question 35

What is unification

Answer 35

The matching algorithm used to choose a particular clause

Question 36

How do two numbers unify

Answer 36

Two numbers unify if and only if they are the same

Question 37

How do two atoms unify

Answer 37

Two atoms unify if and only if they are the same

Question 38

How do variables unify

Answer 38

Two unbound variables, say A and T, always unify, with the
two variables bound to each other.
An unbound variable and a term that is not a variable always
unify, with the variable bound to the term.

Question 39

How do two compound terms unify

Answer 39

Two compound terms unify if and only if they have the same
functor and the same arity, and their arguments can be unified
pairwise, working from left to right.

Question 40

How do two lists unify

Answer 40

Two lists unify if and only if they have the same number of
elements and their elements can be unified pairwise, working
from left to right.

Question 41

How do substitutions work

Answer 41

In general, the result of unification is a substitution
σ = X1/t1, X2/t2, . . . Xn/tn
where ti is a term to be substituted for variable Xi.
This substitution is carried forward to further unifications

Question 42

What is backtracking

Answer 42

If any goal fails, the Prolog system tries to find another way of satisfying the most recently satisfied previous goal.
h :- t1, t2, … tk.

Question 43

How does a logic program generate permutations

Answer 43

It will generate one permutation at a time, on demand from the tester, backtracking to consider
further permutations.

Question 44

Why do purists not like the modification of the database

Answer 44

They see as being against the spirit of logic programming. Like other advanced features, they need to be used with care

Question 45

What is a classical expert system

Answer 45

-A database of elementary facts about the domain;
-Some domain rules for knowledge acquisition;
-Some inference rules for reasoning from data;
-A facility for generating explanations.

Question 46

What are the 4 examples of classical expert systems

Answer 46

-Dendral;
-MYCIN;
-PROSPECTOR;
-SHRDLU.

Question 47

What is Dendral

Answer 47

The 1965 Dendral system (a contraction of DENDRitic ALgorithm) generates all possible arrangements of a set of atoms, and searches through it for likely ones, consistent with
the rules of chemical valence.
The heuristics employed are based on judgment and chemical knowledge — experience and intuition.

Question 48

What is MYCIN

Answer 48

The 1972 MYCIN system (many antibiotics have the suffix “-mycin”) is designed to assist physicians in the diagnosis of bacterial infections.
Knowledge is encoded as 350 decision rules which embody the clinical decision criteria of infectious disease experts.

Question 49

What is PROSPECTOR

Answer 49

The 1976 PROSPECTOR system was designed for decision-making problems in mineral exploration. It aids geologists in evaluating exploration sites or regions for occurrences of ore deposits of particular types.

Question 50

What is SHRDLU

Answer 50

The 1968 SHRDLU system allowed the user to communicate with the computer in natural language, moving objects and querying the state of a simplified “blocks world.”

Question 51

What is blackboard architecture

Answer 51

In expert systems, a blackboard architecture is one where a shared “blackboard” is iteratively updated by a diverse group of knowledge sources, starting with a problem specification and ending with a solution.
The Prolog database readily supports this architecture.

Question 52

What is the difference between static and dynamic predicates

Answer 52

A static predicate cannot be modified as the program runs — by default, predicates are static ones.
A dynamic predicate can be modified as the program runs — predicates may be declared as dynamic ones.

Question 53

How do you add clauses to a database

Answer 53

A clause can be added to the database with:
* asserta( X ) — add a clause X at the beginning of the database;
* assertz( X ) — add a clause X at the end of the database;
* assert( X ) — add a clause X at the beginning of the database.

Question 54

How do you delete clauses from the database

Answer 54

A clause can be removed from the database with:
* retract( X ) — remove a clause X from the database;
* retractall( X ) — remove all facts or clauses that unify with X from the database.

Question 55

What issues can arise from having all functions at the top level?

Answer 55

Name space pollution can occur, clashes caused by reuse of the same name

Question 56

In Haskell what does a where definition do?

Answer 56

A where definition allows one to name a value, and to use it in
an expression.
e.g
sumList :: [ Int ] -> Int
sumList []
= 0
sumList (x:xs)
= x + sxs
where
sxs = sumList xs

Question 57

In Haskell what does a let definition do?

Answer 57

A let definition allows one to name a value, and to use it in an
expression
e.g.
lengthList :: [Int] -> Int
lengthList []
= 0
lengthList (x:xs)
= let
lxs = length xs
in
1 + lxs

Question 58

Define Partial Application in Haskell

Answer 58

Partial application in Haskell refers to the process of supplying a function with fewer arguments than it expects, resulting in a new function that takes the remaining arguments. This allows you to create specialized versions of functions and promotes code reuse and composability.
e.g
– Original function
add :: Int -> Int -> Int
add x y = x + y

– Partial application
addThree :: Int -> Int
addThree = add 3

– Example usage
result :: Int
result = addThree 4

Question 59

Define Curried functions(Indian haha)

Answer 59

A function that takes multiple arguments may be converted into
a succession of functions that each take a single argument.

e.g.
add2 :: Int -> Int -> Int

Question 60

Define uncurried form(not indian haha)

Answer 60

Functions of two or more arguments may also be defined in
uncurried form, this looks like:
multiply2 :: (Int, Int) -> Int

Question 61

Define the pointfree style

Answer 61

The pointfree style means that the arguments of a function
are not explicitly named.
e.g.
minList :: [Int] -> Int
minList xs =
head (sort xs)

would be :

minList2 :: [Int] -> Int
minList2 =
head . sort

Question 62

Note: Haskell functions can be defined using Lambda abstractions

Answer 62

idk what that is it doesnt say - comes later

Question 63

What are the Standard type classes in Haskell

Answer 63

1. Eq;
   2 Ord;
   3 Show;
   4 Read.

Question 64

Define the EQ class

Answer 64

The Eq class provides (==) and (/=) methods.
All basic datatypes except for functions and IO are instances of
this class.

Question 65

Define the Ord Class

Answer 65

The Ord class provides (<=), (<), (>) and (>=) methods.
All basic datatypes except for functions and IO are instances of
this class

Question 66

Define the Show Class

Answer 66

The Show class provides the method
show :: a -> String
All basic datatypes except for functions and IO are instances of
this class
It’s typically used for “unparsers” that output values
e.g.
digits :: Int -> String
digits n
| otherwise = digits d ++ [ chr (ord ’0’ + m) ]
where
(d, m) = n ‘divMod‘ 10

can be written as

digits2 :: Int -> String
digits2 n =
show n

n < 10 = [ chr (ord ’0’ + n) ]

Question 67

Define the read class

Answer 67

The Read class provides the method
read :: String -> a
All basic datatypes except for functions and IO are instances of
this class.
Is typically used for “parsers” that input values

e.g.

number2 :: String -> Int
number2 xs =
read xs

Question 68

Define higher order functions and the three that we need to know

Answer 68

A higher-order function is one that takes a function as an
argument or returns a function as a result.
Three important examples are:

1 map
2 filter
3 foldr

Question 69

Define the map function

Answer 69

The map function applies a function to list elements

Question 70

Define the filter function

Answer 70

The filter function applies a predicate to pick list elements.

Question 71

Define the foldr Function

Answer 71

The foldr function folds a function into list elements.
^idk what that means but coolio

Question 72

Define a list comprehension

Answer 72

A list comprehension expresses one list in terms of the
elements of another. From the first list we generate elements,
which we test and transform to form elements of the result.
[ 2 * n | n <- [5,6,7] ]

Question 73

What is Lazy Evaluation

Answer 73

A lazy functional programming language evaluates the
arguments of functions and of constructors only when
necessary to give a result and then only as far as necessary
to give a result.

Question 74

Define a generator tester structure

Answer 74

The generator/tester structure has a generator component
that generates all values that might be solutions, and tester
component that filters out the values that actually are solutions.

Question 75

What is meant by this statement?
Functional programs must not change the state of the world
when they do calculation

Answer 75

This refers to a key principle in functional programming known as referential transparency or immutability.

In functional programming, functions are expected to be referentially transparent, meaning that their output is solely determined by their input and they have no side effects. This principle extends to the idea that functions should not modify external state or have observable interactions with the outside world during their execution.

Bottom line: there must be no side-effects

Question 76

What is an Action in Haskell

Answer 76

An action is a value of type IO a that, when performed, may do
some input/output, before delivering a value of type a.

Question 77

What does the Then operator do in Haskell

Answer 77

The then operator, (»), performs a first action, discards the result, and performs a second action.

e.g.
putStr2 :: String -> IO ()
putStr2 s
= putStr s&raquo_space; putStr s

Question 78

What does the Bind Operator do Haskell?

Answer 78

The bind operator, (»=), passes the result of performing a
first action to a (parameterised) second action.

e.g.
snooper :: IO ()
snooper
= readFile “/etc/passwd”&raquo_space;=
putStrLn

(»=) :: IO a -> (a -> IO b) -> IO b

Question 79

What does the do notation do in Haskell?

Answer 79

The do notation provides a more convenient notation.
test :: String -> String -> IO String
test fn s
= do writeFile fn s
readFile fn

main :: IO ()
main
= do s <- test “a.txt” “a”
putStrLn s

Question 80

Define the Lambda calculus

Answer 80

The lambda calculus (or λ-calculus) is a formal system for
expressing computation through abstraction and application,
using variable binding and substitution.

Question 81

In the Lambda calculus what are constants

Answer 81

The constants are things like integers, characters, booleans
and operators.
Strictly, speaking, constants are unnecessary.

Question 82

In Lambda calculus what are variables

Answer 82

A variable is a name
^all it says

Question 83

In Lambda calculus what are Applications

Answer 83

An application of a function to an argument is written by
juxtaposition.
Parentheses disambiguate.
looks like (fa)

Question 84

In Lambda calculus what are Functions

Answer 84

A function is described by a λ-abstraction.
A λ-abstraction binds a variable; if there is no λ-abstraction,
then the variable is free

Question 85

What are the three conversion rules in the Lambda calculus

Answer 85

1 alpha conversion;
2 beta conversion;
3 eta conversion

Question 86

What is Alpha conversion

Answer 86

Alpha conversion (α-conversion) allows one to rename bound
variables.
e.g.
(λx.x + 2) ⇒ (λw.w + 2)

Question 87

What is Beta conversion

Answer 87

Beta conversion (β-conversion) allows one to apply a lambda
abstraction to an argument.
(λx.x + 2) 9 ⇒ 9 + 2

Question 88

What is Eta Conversion

Answer 88

Eta conversion (η-conversion) allows one to drop a
λ-abstraction over a function.
(λx.f x) ⇒ f

Question 89

What are some properties(4) of Parallel functional programming

Answer 89

1 concurrency is implicit, not explicit;
2 any shared data needs no protection;
3 reasoning remains easy;
4 results remain determinate

Question 90

What does the statement “Functional programs are blessed with an abundance of parallelism” mean?

Answer 90

Because expressions lack side-effects, they can be evaluated
in any order, or in parallel.

Question 91

What does this statement mean?
Functional programs are cursed by an embarrassment of
parallelism.

Answer 91

Just because an expression could be evaluated in parallel, it
does not mean that it should be evaluated in parallel

Question 92

What are three things that should be considered before creating a task to evaluate an expression

Answer 92

1 is the result going to be useful?
2 is the computation large enough?
3 is there spare processing capacity?

Question 93

What does the Par annotation do?

Answer 93

The pseudo-function par evaluates its arguments in parallel: x
on another processor (if possible), and y on the current
processor.
e.g.
par :: a -> b -> b
par x y = y

Question 94

What does the Seq annotation do?

Answer 94

The pseudo-function seq evaluates its arguments in sequence:
x then y
e.g
seq :: a -> b -> b
seq ⊥ y = ⊥
seq x y = y

Question 95

How is output done in Prolog

Answer 95

With the “write” predicate which displays a term structure, “nl” displays a new line and “writeln” combines the two

Question 96

How is input done in Prolog

Answer 96

With the “read” predicate, which reads a term

Question 97

What are the three classical forms of parallelism in Prolog

Answer 97

-“unification parallelism”;
-“or-parallelism”;
-“and-parallelism”

Question 98

What is unification parallelism

Answer 98

Unification parallelism arises during the unification of the
arguments of a goal with the arguments of a clause head with
the same name and arity. Unification parallelism unifies the arguments of complex structures in parallel.
(e.g [1, f(4)] = [1, R] as R is bound to f(4) i think)

Question 99

Why might it be hard to implement unification parallelism

Answer 99

It might be hard to implement unification parallelism because a substitution must be read/written by multiple processors.

Question 100

What is or-parallelism

Answer 100

Or-Parallelism arises when a goal may be unified with more than one clause in parallel. Or-Parallelism explores the search space generated by the presence of multiple clauses in parallel.
(e.g
f(a).
f(b).
f(c).
^that is three separate functions happening)

Question 101

Why might it be hard to implement or-parallelism

Answer 101

It might be hard to implement or-parallelism because the
parallel implementation must still have sequential behaviour.

Question 102

What is and-parallelism

Answer 102

And-Parallelism arises when more than one subgoal may be
satisfied in parallel. And-Parallelism exploits the presence of more than one
subgoal that may be satisfied in parallel.
(e.g f(a) :- e(1), f(b).)

Question 103

Why might it be hard to implement and-parallelism

Answer 103

It might be hard to implement and-parallelism because the
parallel implementation must account for data dependencies
between subgoals

Question 104

What happened on 2nd September 1945

Answer 104

General Douglas MacArthur invited the
representatives of Japan and the Allies to sign a surrender
document ending World War 2.
(not relevant but its in the lecture notes and made me laugh)

Question 105

What did the Ministry of International Trade and Industry (MITI) do

Answer 105

MITI excelled in working with the private sector
closely but neutrally, knowing different plans and problems of
individual firms, and coordinating and guiding them. They were repsonsible for the Fifth Generation Project

Question 106

What is the Fifth Generation Project

Answer 106

The Fifth Generation Project was intended to:
* make Japan a leader in the computer industry by
developing knowledge information processing systems
built using logic programming.
* stimulate original research, making the results widely
available, so refuting accusations that Japan exploits
knowledge from abroad without contributing any of its own

Question 107

Why was logic programming chose for the Fifth Generation Project

Answer 107

Logic programming was chosen because it unifies innovations in:
-software engineering;
-databases;
-artificial intelligence;
-computer architecture.

Question 108

Explain software engineering in terms of logic programming

Answer 108

In the field of software engineering, logic programs can serve as executable specifications, that can be made more efficient by program transformation

Question 109

Explain databases in terms of logic programming

Answer 109

In the field of databases, logic programs have been shown to
be adequate both as a query language, and for describing
integrity constraints

Question 110

Explain artificial intelligence in terms of logic programming

Answer 110

In the field of artificial intelligence, logic programs naturally implement rules of the form A if B1 and . . . and Bn

Question 111

Explain computer architecture in terms of logic programming

Answer 111

In the field of computer architecture, logic programs provide a way to overcome the von Neumann bottleneck through single assignment.

Question 112

What is a finite state automaton

Answer 112

A Finite State Automaton (FSA), is a model of computation based on the idea of a system changing state due to inputs supplied to it, until a final or acceptor state is reached.

Question 113

Why a finite automata useful

Answer 113

They are a useful model for many important kinds of
hardware and software (e.g representing process states on a processor)

Question 114

What are the central concepts of automata theory

Answer 114

-alphabets;
-strings;
-languages.

Question 115

What is an alphabet in terms of FSA

Answer 115

An alphabet, Σ, is a finite, nonempty set of symbols.
Example:
Σ = a, b, . . . z

Question 116

What is a string in terms of FSA

Answer 116

A string is a finite sequence of symbols chosen from some
alphabet. The set of all possible strings over an alphabet Σ is Σ∗.
Example:
bccd is a string drawn from Σ = a, b, . . . z.

Question 117

What is a language in terms of FSA

Answer 117

If Σ is an alphabet, and L ⊆ Σ∗, then L is a language over Σ.
Example:
{abc, def, ghi} is a language drawn from Σ∗, where
Σ = a, b, . . . z.

Question 118

What does a deterministic finite automata (DFA) consist of

Answer 118

-a finite set of states;
-a finite set of input symbols;
-a transition function;
-a start state;
-a set of accepting or final states.

Question 119

How are states represented in DFA

Answer 119

The finite set of states is often denoted Q.
Each state may be drawn as a circle.

Question 120

How are input symbols represented in DFA

Answer 120

The finite set of input symbols is often denoted Σ.
Each symbol may be drawn as a label of a transition arrow (so just either numbers or letters labelling the arrows)

Question 121

How are transition functions represented in DFA

Answer 121

The transition function may be described by a number of cases,
δ(p, a) = q.
Each case, δ(p, a) = q, may be drawn as an arrow from the
circle for p to the circle for q, labelled a.

Question 122

How is the start state represented in DFA

Answer 122

The start state, q0, is one of the states in Q.
The arrow drawn into the start state q0 is labelled Start.

Question 123

How is the accepting/final state represented in DFA

Answer 123

The accepting or final states are a subset of Q. The machine
may halt in accepting states provided it has no input left.
All other states become rejecting states if there is no input left.
Final or accepting states are marked by double circles.

Question 124

What is the difference between deterministic and non-deterministic automata

Answer 124

• on each input, a deterministic automaton can transition
  from its current state to another state;
• on each input (or on no input), a nondeterministic
  automata can transition form its current state to several
  states.

Question 125

What is regular expression

Answer 125

A regular expression provides an algebraic (and so
declarative) description of a deterministic or nondeterministic
finite state automaton.

Question 126

What are the three operations for regular expressions

Answer 126

The algebra of regular expressions combines constants and variables denoting languages using three operations:
-closure;
-concatenation;
-union.

Question 127

What is the closure operation

Answer 127

The closure of a language L is denoted L∗.
It represents the set of those strings that can be formed by
taking any number of strings from L, and concatenating them.
The “*” operator has the highest precedence — it applies to the
smallest sequence of symbols to its left.

Question 128

What is the concatenation operation

Answer 128

The concatenation of languages L and M is denoted LM.
It is the set of strings that can be formed by taking any string in
L and appending any string in M.
Concatenation has the next highest priority — expressions that
are juxtaposed are grouped together.

Question 129

What is the union operation

Answer 129

The union of two languages L and M is denoted L + M.
It is the set of strings that are either in L or M, or both.
The “+” operator has the lowest priority — expressions may be
grouped by unions in any order.

Question 130

Just some examples of regular expression

Answer 130

0* + 1 means any number of 0s or a 1
101* means 10 and any number of 1s
10 + 01 means 10 or 01
0(10)* means 0 and any number of 10s