Studied by 18 people
Draw state transition diagrams for deterministic or nondeterministic finite automata (DFAs/NDFAs) that recognise each of the following languages:
a) L1 = {w : {0, 1} ∗ |w contains exactly two 0s}
(Describe how you would draw it)
Loops at the start state handle any elements that are not in the language requirements, e.g. the 1 loops get rid of any potential 1’s
Draw state transition diagrams for deterministic or nondeterministic finite automata (DFAs/NDFAs) that recognise each of the following languages:
b) L2 = {w : {0, 1} ∗ |w contains at least one 000}
(Describe how you would draw it)
Explain the relation between Deterministic Finite Automata, regular languages, regular grammar, and regular expressions
grammars generate languages
NDFA’s/DFA’s recognise languages
Expressions denote languages
Explain what an undecidable problem is and give an example of such a problem
An undecidable problem is one where we cannot determine if a given algorithm will produce a result with a provided input for example if a Turing machine will halt or not, the halting problem
What does the Church-Turing thesis state and explain both the implication and limitation of the thesis for electronic digital computers
The church-turing thesis states that any algorithmic process can be executed by the universal turing machine however the implication is that digital computers can face the same limitations which is they cannot solve undecidable problems
Explain how finding a solution to the satisfiability (SAT) problem in polynomial time would solve all NP-Complete problems
If the satisfiability (SAT) problem could be solved quickly (in polynomial time), then every other problem with a similar level of complexibility can also be solved quickly. SAT is a fundamental problem that captures the essence of hard problems.
What is the difference between an NDFA and an DFA?
Deterministic Finite Automata (DFA) follows a single path for every input while an NDFA has several possible paths it can travel
Explain what is meant by determinism and non-determinism
determinism implies predictability and single-choice behaviour, while non-determinism introduces the possibility of multiple choices or outcomes for a given state and input.
Give a regular expression for this language.
Give the grammar that generates this language
1 ∗01∗01∗
Give a regular expression for this language.
Give the grammar that generates this language
(0 + 1) ∗000(0 + 1) ∗
Design a Turing Machine that performs the addition of two integers: given two strings of 1’s on the Turing tape as input, separated by a blank symbol (#), the machine should halt with a single string of 1’s, whose length is the number of elements of string one plus the number of elements in string two. You can assume that the first integer is non-zero. So, for example, if the first string has length 3 and the second has length 2, we wish to move from |1 | 1 | 1 | # | 1 | 1 | # | # | . . . | to |1| 1 | 1 | 1 | 1 | # | # | # | . . . |
You should use the following algorithm: 1 Scan right across tape to find end marker of string one (#) 2 Replace # with 1 3 Scan right across tape to find end marker of string two (#) 4 Move left one step 5 Replace 1 with # 6 Scan left across tape until home Hint: an example of a label for an arc in your Turing Machine would be 1/1, R.
Describe how you would draw the diagram
Reduce each of the following expressions
(λy. + y y)((λy. + y y) 4)
Note that there is more than one reduction order here, they could reduce the leftmost lambda first instead. This is actually quite a hard one to start with, so please award some marks for a reasonable attempt.
(λy. + y y)((λy. + y y) 4)
→(λy. + y y)( + 4 4)
→(λy. + y y) 8
→( + 8 8)
→16
(λy. + y y)((λy. + y y) 4) (EXPLANATION)
Inner Beta Reduction:
We start with the expression (𝜆𝑦.+ 𝑦 𝑦)((𝜆𝑦.+ 𝑦 𝑦) 4).
We apply the inner lambda abstraction to the argument 4. According to beta reduction, we replace every occurrence of 𝑦 in + 𝑦 𝑦 with 4, in short 8.
This results in (𝜆𝑦.+ y y )(𝜆𝑦.+ 4 4).
Outer Beta Reduction:
Now, we have (𝜆𝑦.+ y y) 8. We apply the outer lambda abstraction to 8.
According to beta reduction, we replace every occurrence of 𝑦 in + 𝑦 𝑦 with + 4 4.
This results in + (+ 4 4) (+ 4 4).
Simplify Expression:
We have + (8) (+8). We can simplify this expression by performing the addition operations.
This results in 16
Reduce: (λu. u 3)(λv. ∗ u v)
(λu. u 3)(λv. ∗ u v) →(λv. ∗ u v) 3 → ∗ u 3
Beta Reduction:
We start with the expression (𝜆𝑢.𝑢 3)(𝜆𝑣.∗ 𝑢 𝑣)(λu.u3)(λv.∗uv).
First, we apply the inner lambda abstraction (𝜆𝑣.∗ 𝑢 𝑣)(λv.∗uv) to the argument 33. According to beta reduction, we replace every occurrence of 𝑣v in ∗ 𝑢 𝑣∗uv with 33.
This results in (𝜆𝑣.∗ 𝑢 𝑣)3(λv.∗uv)3.
Simplify Expression:
Now, we have (𝜆𝑣.∗ 𝑢 𝑣)3(λv.∗uv)3. This means that 𝑣v is replaced by 33 in ∗ 𝑢 𝑣∗uv, so the expression becomes ∗ 𝑢 3∗u3.
Therefore, by applying beta reduction according to the rules of lambda calculus, we obtained the final result ∗ 𝑢 3∗u3. The reduction involved applying the lambda abstraction to its argument and performing the necessary substitution.
reduce: (λx. (λy. (λz. ∗ (+ 3 z) y)) 8) x) 5
There is more than one reduction order, e.g. Normal order reduction:
(λx. (λy. (λz. ∗ (+ 3 z) y)) 8) x) 5
→(λy. (λz. (∗ (+ 3 z) y)) 8) 5
→(λz. (∗ (+ 3 z) 5)) 8 →(∗ (+ 3 8) 5)
→(∗ 11 5)
→55
or
Applicative order reduction: (λx. (λy. (λz. (∗ (+ 3 z) y)) 8) x) 5
→(λx. (λy. (∗ (+ 3 8) y)) x) 5
→(λx. (λy. (∗ 11 y)) x) 5
→(λx. (∗ 11 x)) 5
→(∗ 11 5)
→55
reduce: (λx. (λy. (λz. ∗ (+ 3 z) y)) 8) x) 5 (EXPLAINED)
Let's break down the reduction steps for the expression (𝜆𝑥.(𝜆𝑦.(𝜆𝑧.∗ (+ 3 𝑧) 𝑦)) 8) 𝑥) 5 using both normal order reduction and applicative order reduction:
Normal Order Reduction:
We start with the expression (𝜆𝑥.(𝜆𝑦.(𝜆𝑧.∗ (+ 3 𝑧) 𝑦)) 8) 𝑥) 5.
In normal order reduction, we first reduce the outermost lambda expression.
Applying the outermost lambda abstraction to 5, we replace every occurrence of 𝑥x with 5. This results in (𝜆𝑦.(𝜆𝑧.∗ (+ 3 𝑧) 𝑦) 8) .
Next, we apply the next lambda abstraction to 5, replacing every occurrence of 𝑦y with 5. This results in (𝜆𝑧.∗ (+ 3 𝑧) 5) 8.
Finally, we apply the last lambda abstraction to 8, replacing every occurrence of 𝑧 with 8. This results in ∗ (+ 3 8) 5∗.
Simplifying the expression, we get ∗ 115, which equals 55.
Applicative Order Reduction:
We start with the expression (𝜆𝑥.(𝜆𝑦.(𝜆𝑧.∗ (+ 3 𝑧) 𝑦)) 8) 𝑥) 5.
In applicative order reduction, we first reduce the innermost lambda expression.
Applying the innermost lambda abstraction to 8, we replace every occurrence of 𝑧 with 8. This results in (𝜆𝑦.∗ (+ 3 8) 𝑦).
Next, we apply the next lambda abstraction to 5, replacing every occurrence of 𝑦 with 5. This results in ∗ (+ 3 8) 5.
Simplifying the expression, we get ∗ 11 5, which equals 55.
Therefore, both normal order reduction and applicative order reduction lead to the same final result of 55. The reduction involved applying lambda abstractions to their arguments and performing the necessary substitutions.
What is a horn clause
A Horn clause contains at most disjunction, negation and one positive predicate.
For each of the following clauses, state if they are Horn clauses or not.
i) vegetable(carrot) ∨ orange(carrot)
No
two positive predicates. Note that the wording of this question just asks whether it is a Horn clause, not why. So if they say ”Yes” or ”No” and they are correct, then the full 2 marks should be awarded, for each part.
For each of the following clauses, state if they are Horn clauses or not.
¬fruit(carrot) ∧ vegetable(carrot) ∨ ¬green(carrot)
No, no conjunction allowed
In logic, a conjunction is a logical operation that connects two statements, and it is represented by the symbol "∧", which is read as "and".
In the expression ¬fruit(carrot)∧vegetable(carrot)∨¬green(carrot)¬fruit(carrot)∧vegetable(carrot)∨¬green(carrot), the symbol "∧" is used to denote conjunction. However, since the task specifies that only Horn clauses are allowed, and Horn clauses do not permit conjunctions, this expression does not qualify as a Horn clause. Therefore, the answer is "No".
For each of the following clauses, state if they are Horn clauses or not.
¬fruit(carrot) ∨ vegetable(carrot) ∨ ¬green(carrot)
Yes.
This expression qualifies as a Horn clause because it adheres to the criteria:
At Most One Positive Predicate: The clause contains exactly one positive predicate, which is "vegetable(carrot)".
Negative Predicates: The clause also includes negative predicates represented by the symbols ¬, such as "¬fruit(carrot)" and "¬green(carrot)".
Since the clause satisfies the conditions of having at most one positive predicate and including negative predicates, it qualifies as a Horn clause.
we are using the method of Reduction ad Absurdum (RAA), also known as proof by contradiction, to show that Mary drives a car. Here's how the proof is completed:
Premises:
𝑆1S1: If Mary has money, then she will buy a car.
𝑆2S2: If Mary buys a car, then she will drive it.
𝑆3S3: Mary has money.
Assumption for Proof by Contradiction:
𝑆4S4: We assume the negation of what we want to prove, which is that Mary does not drive a car (¬drive(mary, car)¬drive(mary, car)).
Inference:
From 𝑆1S1 and 𝑆3S3, we can infer that Mary buys a car (𝑆5:buy(mary, car)S5:buy(mary, car)). This is based on the premise that if Mary has money, she will buy a car.
Inference:
Using 𝑆2S2 and 𝑆5S5, we can infer that Mary drives the car (𝑆6:drive(mary, car)S6:drive(mary, car)). This follows from the premise that if Mary buys a car, she will drive it.
Contradiction:
We now have both ¬drive(mary, car)¬drive(mary, car) (from 𝑆4S4) and drive(mary, car)drive(mary, car) (from 𝑆6S6). This is a contradiction.
Conclusion:
The presence of a contradiction means our initial assumption (¬drive(mary, car)¬drive(mary, car)) must be false.
Final Step:
We conclude that Mary does indeed drive a car (𝑆7S7).
Consider the language
L = {x nymx n | m, n ∈ N}.
i) Give the matching context-free grammar for the language L.
S → xSx | T T → yT | λ
Start Symbol 𝑆S:
The start symbol 𝑆S is used to generate strings of the form 𝑥𝑛𝑦𝑚𝑛xnymn.
The production rule 𝑆→𝑥𝑆𝑥S→xSx generates strings with an equal number of 𝑥x's on both sides of the 𝑆S non-terminal, effectively ensuring that there are 𝑛n 𝑥x's on the left side and 𝑛n 𝑥x's on the right side.
This rule allows the generation of strings like 𝑥𝑥𝑆𝑥𝑥xxSxx or 𝑥2𝑆𝑥2x2Sx2, where 𝑆S generates the middle part of the string.
Non-Terminal 𝑇T:
The non-terminal 𝑇T is introduced to generate the 𝑦y characters in the string.
The production rule 𝑇→𝑦𝑇T→yT generates strings with an arbitrary number of 𝑦y's, representing the 𝑦y characters in the middle of the string.
The rule 𝑇→𝜆T→λ allows for the possibility of having no 𝑦y's in the string, representing the empty string case.
Combining Rules:
By combining the rules for 𝑆S and 𝑇T, we can generate strings of the form 𝑥𝑛𝑦𝑚𝑛xnymn, where 𝑛n and 𝑚m can be any natural numbers.
The rule 𝑆→𝑥𝑆𝑥S→xSx ensures that the number of 𝑥x's on the left side of 𝑆S is the same as the number of 𝑥x's on the right side, ensuring the equality of 𝑚m and 𝑛n.
Design a Turing Machine that performs the subtraction of two unary integers. Given two strings on the Turing tape as input, the machine should halt in the accept state with the result that is the number of elements of string one minus the number of elements in string two. The machine needs only to consider cases where the result is zero or positive.
a) Provide the algorithm of this Turing machine, using English descriptions, or code, or pseudo-code, where appropriate.
(It is helpful to draw this one out)
Marks will be awarded for partial or inconclusive algorithms. A possible answer may be:
1 scan forward across tape to find end marker of string one
2 skip end marker
3 scan forward across tape to find end marker of string two
4 go back one step
5 scan backward across tape to find last symbol of string two
6 remove last symbol of string two
7 scan backward across tape to find end marker of string one
8 go back one step
9 scan backward across tape to find last symbol of string one
10 remove last symbol of string one
11 loop back to item
3 Accept state should be reached when no more symbols are found in string two, in step 5.
Reject state should be reached if a symbol has been removed from string two but no symbols have been found in string one (step 9).
Design a Turing Machine that performs the subtraction of two unary integers. Given two strings on the Turing tape as input, the machine should halt in the accept state with the result that is the number of elements of string one minus the number of elements in string two. The machine needs only to consider cases where the result is zero or positive.
Provide the implementation of your design as the state transition diagram of your Turing Machine.
Give the state transition diagrams for deterministic or non-deterministic finite automata (DFAs or NDFAs) that recognise the languages represented by the following regular expressions:
(ab)∗
(ab)∗ + (aba)∗
(ab + ba)+(aa + bb)∗
Consider the regular expression ((a + b)(a + b)∗a)∗
a) Give the state transition diagram of a Non-Deterministic Finite Automaton that recognises this regular expression.
The transition table and conversion to DFA:
For each of the following clauses, state if they are Horn clauses or not.
¬kind(john) ∨ dog(john) ∨ furry(dog(john)
No, two positive predicates.
In the expression ¬kind(john)∨dog(john)∨furry(dog(john))¬kind(john)∨dog(john)∨furry(dog(john)), positive predicates represent statements that are asserted or affirmed to be true. Positive predicates are those that do not include negation.
Here's where you can find the positive predicates:
dog(john)dog(john) is a positive predicate because it asserts that "john" is a dog.
furry(dog(john))furry(dog(john)) is also a positive predicate because it asserts that "dog(john)" is furry.
Since there are two positive predicates (dog(john)dog(john) and furry(dog(john))furry(dog(john))), the expression does not meet the criteria for a Horn clause, which allows at most one positive predicate. Therefore, the answer is "No."
¬kind(john) ∨ dog(john) ∨ ¬furry(dog(john)
yes
In the expression ¬kind(john)∨dog(john)∨¬furry(dog(john))¬kind(john)∨dog(john)∨¬furry(dog(john)), there is only one positive predicate, which is dog(john)dog(john). The other two predicates, ¬kind(john)¬kind(john) and ¬furry(dog(john))¬furry(dog(john)), are negative predicates because they include negation.
Since there is only one positive predicate and multiple negative predicates, the expression meets the criteria for a Horn clause. According to the definition of a Horn clause, it can have at most one positive predicate, and any number of negative predicates. Therefore, the expression qualifies as a Horn clause, and the answer is "Yes."
Use the following premises to draw the conclusion and then use denial (Reduction ad Adsurdum) to prove or disprove your conclusion:
P1: All the old things in this cupboard are broken.
P2: No jug in this cupboard is new.
P3: Nothing in this cupboard, that is broken, can hold water.
S1: ∀X.old(X) → broken(X)) Assumption
S2: ∀Y.jug(Y) → old(Y) Assumption
S3: ∀Z.broken(Z) → ¬hold water(Z) Assumption
Reduction ad Absurdum (RAA) Example Flashcard:
Assumption: Start by assuming the opposite (negation) of the conclusion. In this case, assume the opposite of the statement you want to prove, which is that all jugs that can hold water are not new.
Logic Chain: Use premises and assumptions to deduce consequences. In this case, follow the logical implications of the assumptions and premises provided.
Universal Quantification: All premises and assumptions apply to every element in their domain. In this case, consider how the assumptions apply universally to all relevant elements, such as old things and jugs.
Contradiction: Identify a contradiction between the assumption and the premises. In this case, find where the assumption contradicts the premises, such as a new jug that can hold water.
False Assumption: Conclude that the assumption (negation of the conclusion) is false. In this case, if the assumption leads to a contradiction, it must be false, leading to the truth of the original statement.
True Conclusion: Therefore, the original statement (the conclusion) must be true. In this case, if the assumption is false, then the original statement, that all jugs that can hold water are not new, must be true.
For each of the following, use β reduction to reduce the following expressions, using α conversion first to rename variables and avoid name capture, if necessary.
i) (λy. ∗ y y) 4
In this problem, we are performing β reduction on the lambda expression (𝜆𝑦. 𝑦⋅𝑦) 4. Before we proceed with β reduction, let's first check if there's any potential name capture.
Check for Name Capture:
In this expression, there's no risk of name capture because the variable 𝑦 is locally scoped within the lambda abstraction.
Perform β Reduction:
Replace all occurrences of the bound variable 𝑦 with the argument 4.
(𝜆𝑦. 𝑦⋅𝑦) 4 becomes 4⋅4
The result of 4.4 is 16
What is name capture
Name capture in lambda calculus happens when a variable inside a lambda expression gets unintentionally affected by the same name used outside the expression. This can change the expression's meaning unexpectedly. To prevent this, we use α-conversion, which means renaming variables to avoid conflicts. For example, in the expression (𝜆𝑥. 𝜆𝑦. 𝑥+𝑦) 𝑦, we need to make sure the 𝑦 inside the inner lambda isn't accidentally affected by the 𝑦 outside.
For each of the following, use β reduction to reduce the following expressions, using α conversion first to rename variables and avoid name capture, if necessary.
(λx. λy. x y) (λx. y x)
To prevent name capture, we perform α-conversion, which involves renaming variables to avoid conflicts. In this case, we'll rename the bound variable 𝑥x in the second lambda expression to 𝑧z, ensuring it's distinct from the 𝑥x in the first lambda expression.
After α-conversion, the second lambda expression becomes (𝜆𝑧. 𝑦 𝑧).
Now, we can substitute the second lambda expression into the first one without worrying about name capture:
(𝜆𝑥.𝜆𝑦. 𝑥 𝑦) (𝜆𝑥. 𝑦 𝑥)→(𝜆𝑥.𝜆𝑦. 𝑥 𝑦) (𝜆𝑧. 𝑦 𝑧)(λx.λy.xy)
By applying β-reduction, where we replace all occurrences of the bound variable (𝑥x in this case) with the argument (𝜆𝑧. 𝑦 𝑧λz.yz), we get:
(𝜆𝑦. (𝜆𝑧. 𝑦 𝑧) 𝑦)(λy.(λz.yz)y)
Now, there's no risk of name capture, and the expression has been successfully simplified.
Reduce the following expression
(λx. (λy. (λz. (× (− z 2) y)) 12) x) 6
i) using Normal Order Reduction
Normal order reduction is a strategy in lambda calculus where we always substitute the outermost, leftmost redex (reducible expression) first. In simpler terms, we always choose the leftmost lambda abstraction to reduce first.
In the given expression (𝜆𝑥. (𝜆𝑦. (𝜆𝑧. (× (− 𝑧 2) 𝑦)) 12) 𝑥) 6, to reduce it using normal order reduction:
We start by substituting the outermost, leftmost redex, which is (𝜆𝑥. (𝜆𝑦. (𝜆𝑧. (× (− 𝑧 2) 𝑦)) 12) 𝑥), with the argument 6. This gives us (𝜆𝑦. (𝜆𝑧. (× (− 𝑧 2) 𝑦)) 12) 6.
Next, we substitute the next leftmost redex, which is (𝜆𝑦. (𝜆𝑧. (× (− 𝑧 2) 𝑦)) 12), with the argument 6. This gives us (𝜆𝑧. (× (− 𝑧 2) 6)) 12.
Finally, we substitute the last redex, which is (𝜆𝑧. (× (− 𝑧 2) 6)), with the argument 12. This gives us (× (− 12 2) 6).
We then evaluate the expression to get (× 10 6), which simplifies to 60.
So, using normal order reduction, the expression reduces to 60.
Reduce the following expression
(λx. (λy. (λz. (× (− z 2) y)) 12) x) 6 using Applicative Order Reduction
First Redex (Innermost):
We identify the innermost redex, which is (𝜆𝑧. (× (− 𝑧 2) 𝑦)) 12.
We substitute the argument 12 into the lambda abstraction for 𝑧
This substitution results in (𝜆𝑦. (× (− 12 2) 𝑦)) 6.
Second Redex (Next Innermost):
Now, we identify the next innermost redex, which is (𝜆𝑦. (× (− 12 2) 𝑦)).
We substitute the argument 6 into the lambda abstraction for y
This substitution results in (× (− 12 2) 6).
Third Redex (Outermost):
Finally, we identify the outermost redex, which is (× (− 12 2) 6).
We evaluate the expression by performing the multiplication and subtraction operations.
This evaluation results in the final value 60.
Design a Turing Machine that performs the subtraction of two unary integers. Given two strings on the Turing tape as input, the machine should halt in the accept state with the result that is the number of elements of string one minus the number of elements in string two.
The machine needs only to consider cases where the result is zero or positive. a) Provide the algorithm of this Turing machine, using English descriptions, or code, or pseudo-code, where appropriate.
1 scan forward across tape to find end marker of string one
2 skip end marker
3 scan forward across tape to find end marker of string two
4 go back one step
5 scan backward across tape to find last symbol of string two
6 remove last symbol of string two
7 scan backward across tape to find end marker of string one
8 go back one step
9 scan backward across tape to find last symbol of string one
10 remove last symbol of string one
11 loop back to item
Accept state should be reached when no more symbols are found in string two, in step 5.
Reject state should be reached if a symbol has been removed from string two but no symbols have been found in string one (step 9).
Design a Turing Machine that performs the subtraction of two unary integers. Given two strings on the Turing tape as input, the machine should halt in the accept state with the result that is the number of elements of string one minus the number of elements in string two.
Provide the implementation of your design as the state transition diagram of your Turing Machine.
Draw state transition diagrams for deterministic (or nondeterministic) finite automata (DFAs/NDFAs) that recognise each of the following languages:
a) L1 = {w : {0, 1} ∗ |w contains exactly one 1}
describe it, is it an NDFA/DFA?
0 ∗10∗
L3 = {w : {0, 1} ∗ |w contains at least one 0 and at least one 1}
Describe it, is it an NDFA/DFA?
(0 + 1) ∗0(0 + 1) ∗1(0 + 1) ∗
A → 0A | 0B | 1A
B → 0B | 1B | 1C
C → 0C | 1C | λ
L4 = {w : {0, 1} ∗ |w contains the string 01 or the string 10}
describe it, is it an NDFA/DFA?
(0 + 1) ∗ (01 + 10)(0 + 1) ∗
A → 0A | 1A | 1B | 0C
B → 0D
C → 1D
D → 0D | 1D | λ
Explain why a Push down Automata with a single stack device can recognise more complex languages than a regular language
Pushdown Automata recognises context-free languages and uses a single stack device as it can keep track of multiple variables that are being pushed on and popped out of the stack to allow multiple variables to be tracked for complex languages.
Regular languages cannot recognise recursion.
Note
Flashcard