Suppose that we have a finite automaton A1 that accepts
some set of strings S1, and we have a second finite
automaton A2 that accepts another set S2.
If we combine the two automata by merging the start
state of A2 with the accepting state of A1 (and
making that merged node a non-accepting state),
what is the set of strings accepted by the new
automaton?

A: All strings of S1 that are not in S2.
B: The intersection of S1 and S2.
C: The union of S1 and S2.
D: The set concatenation of S1 and S2.
E: All strings of S2 that are not in S1.
ANS:D


What regular expression represents the set of
all binary (base 2) strings
ending with 101?
A: 1*0*1*
B: 1+0+1+
C: 0*1+01
D: (0|1)*101
E: (01)*101
ANS:D

In logic, an atomic proposition, with a possible negation
sign in front of it is called a
A: unifier
B: clause
C: rule
D: literal
E: predicate
ANS:D

Which of the following is a Horn clause?
A: P V Q
B: P ^ Q
C: P V ~Q V ~R
D: ~P ^ ~Q
E: ~~(P ^ Q ^ R)
ANS:C

What should a unification algorithm return for the pair,
P(x, f(x)), P(y, y)$ ?
A: {}
B: {y/x}
C: {x/y, f(x)/y}
D: {f(x)/y}
E: not unifiable
Ans: E

Reduce the lambda calculus expression
Lx (f(x),f(x)) (Ly g(y))

A: (f(Ly g(y)),f(Ly g(y)))
B: (f(y),f(y))
C: Ly g(y) Ly g(y)
D: (f(g(y)), f(g(y)))
E: Lx (f(x),f(x)) y
ANS:A