Updated Answers PDF

Item 1 The difference between a Finite State Machine and a Turing Machine is that: A A Turing Machine is simpler than a finite State machine B A Turing Machine has a start state and a Finite State Machine does not. C A Finite State Machine has more c...

Item 1 The difference between a Finite State Machine and a Turing Machine is that: A A Turing Machine is simpler than a finite State machine B A Turing Machine has a start state and a Finite State Machine does not. C A Finite State Machine has more computational power than a Turing Machine A Turing Machine has more memory than the Finite state machine. D  Item 2 Given the state diagram of a Turing Machine is: The Tape input language ∑ = A {a, L, R} B {a, b, c}  C {a,L} D {a,b,c,L} Item 3 Given the following state diagram of the Turing Machine An illegal input on a tape would be: Choose all that apply.There may be more than one correct answer. A 1Δ  B 0101Δ  C 0110Δ D 0100Δ  Item 4 Given the state transition diagram of a Turing Machine: and a tape: 0110Δ. What is the result of the tape after computing the machine? A 0110Δ B XY10Δ  C XYXYΔ D X1XYΔ Item 5 Given the following state diagram of the Turing Machine A legal input on a tape would be: Choose all that apply. There may be more than one correct answer. A 1Δ B 0101Δ C 0110Δ  D 010Δ  Item 6 Let 𝐴={1,3,5},𝐵={5, 3, 1},𝐶={1,3},𝐷={1,5}. Which of the following is true? A 𝐵 ⊂𝐴 B 𝐶⊆𝐴  C 𝐷⊈𝐴 D 𝐶=𝐴 Item 7 Which of the following is true? A apple ∉ {apple, banana, orange} B {orange} ∈ {apple, banana, orange} C banana ∈ |{apple, banana, orange}| D |{apple, banana, orange}| = 3  Item 8 Given the following input/output table, what will be the Boolean Expression corresponding to this table? Note: D, E, F are input columns, while G is an output column. Input Output D E F G 1 1 1 0 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 A (D ∧ E ∧ ~F) ∨ (D ∧ ~E ∧ ~F)  B (D ∨ E ∨ F) ∨ (~D ∧ ~E ∧ ~F) (D ∨ E ∨ ~F) ∧ (~D ∨ E ∨ F) C (D ∨ E ∨ ~F) ∧ (D ∨ ~E ∨ ~F) D Item 9 Which of the following is true? Choose all that apply. There may be more than one answer. With a Turing machine we can solve any decision problem that can be solved with a Laptop or PC A running Linux\Windows.  According to the Church-Turing thesis all algorithmically solvable problems can be solved by a Turing B machine.  C Undecidable problem is a problem that cannot be solved using a Turing Machine.  The undecidability of the halting problem is a statement about Turing machines, it is not applicable to D real computers. Item 10 Consider a statement of the form ∀x∈ R: P(x) → Q(x) Its converse will be: A ∀x∈ R: P(x) → ~Q(x) B ∀x∈ R: ~Q(x) → P(x) C ∀x∈ R: Q(x) → P(x)  D ∀x∈ R: ~P(x) → ~Q(x) Item 11 Consider the following universal conditional statement: “If a real number is greater than 4, then its square is greater than or equal to 8.” What will be the inverse of the above universal conditional statement? A If a real number is less than or equal to 4, then its square is less than 8  B If the square of a real number is greater than or equal to 8, then the number is greater than 4 C If a the square of a real number is less than 8, then the number is less than or equal to 4 The statement remains the same D Item 12 Which of the following can be expressed in predicate logic, but not in a propositional logic? If Darrell is a second year CS student, he has passed CS1005 A Darrell is a second year CS student Therefore, Darrell has passed CS1005 B Darrell goes into second year CS class if he has passed CS1005 C Darrell proceeds into second year CS if and only if he has passed CS1005 Every second year CS student must have passed CS1005 D Darrell is a second year CS student  So, Darrell must have passed CS1005 Item 13 Which of the following arguments are valid? p→q A q→p Therefore p ⋁ q p→q B ~p Therefore ~ q p⋁q C p→r q→r  Therefore r p ⋁ (q ⋀ r) D ~(p ⋀ q) Therefore r Item 14 Which of the following is a contradiction? A ~(p ⋀~p) (~p ⋁ q) ⋁ (p ⋀~q) B C ~((p ⋀ q) →p)  D (p → (q →r)) ↔︎ ((p ⋀q) →r) Item 15 Referring to the following circuit diagram What is the output at Signal R as a logical expression for the above circuit diagram? A (p ⋀ q) ⋁ ~r B (~p ⋀ q) ⋁ ~q  C (~q ⋁ ~p) ⋁ ~p D ~(p ⋁ ~q) ⋀ ~q Item 16 Which of the following is the propositional form of the sentence: Smith flies to US for holiday if he has a valid passport, a visa, and enough money? A d → (a ⋀ b ⋀ c) B (a ⋀ b ⋀ c) → d  C a → (b ⋀ c ⋁ d) D a → (b ⋁ c ⋀ d) Item 17 What is a Turing machine? A A type of computer used for solving complex mathematical problems. A theoretical model for computing machines that can solve any problem that can be solved by an B algorithm.  C An electronic device designed for performing a specific set of tasks. D A type of computer program used for writing letters and documents. Item 18 Consider the following grammar given in Backus-Naur Form. Which of the following words can be recognised by the grammar. The start rule is : A 12345 B Z3  C H9876 D hello Item 19 Choose the statement that is true? A context free grammars are a subset of regular grammars B regular grammars are a subset of context free grammars  C context free grammars and regular grammars are not in a subset relation D none of the given answers is correct Item 20 Which of the following regular expressions are equivalent? Choose all that apply. There may be more than one correct answer. A (a|b)∗ = (a|b)∗(b|a)∗  B (a|b)∗ = a(a|b)∗ C (a|b)∗ = (a|b)∗ |(a|b)∗  D (a|b)∗ = (a∗|b∗) Item 21 Which of the following regular expressions represents all strings which have a double letter somewhere in them: A (a|b)*(aa|bb)(a|b)*  B (a|b)*(aa|bb) C (aa|bb)(a|b)* D (a|b)*(ab*|ba*) Item 22 Describe in English the languages associated with the following regular expressions a(a | bb)* A none of the answers is correct B an a followed by at least one a or 2 b’s C an a followed by zero or more of one a or 2 b’s  D two a's followed by 2 b’s Item 23 You are given the following argument and its corresponding truth table. The argument is p→~q, ~q→~r. Therefore p→~r Choose the correct statement. A The critical rows of the table are 4, 5, 6, 8 and the argument is VALID  B The critical rows of the table are 1, 3 and the aregument is NOT VALID C The critical rows are 2, 4, 6, 8 and the argument is VALID D There are no critical rows and the validity of the argument cannot be determined. Item 24 Given the predicate buy(x, y), which stands for x likes y, Choose all CORRECT translations of propositional formulas to English. Choose all that apply. There may be more than one correct answer. A ∀x.(buy(Mark, x) → buy(Jane, x)) means "Jane buys everything that Mark buys."  B ​∃x∀y.buy(x, y) means "Someone buys everything."  C ∃x.buy(Mark, x) means "Mark buys everything." D ​∀x.buy(x, Chocolate) means "Someone buys chocolate" Item 25 What is the contrapositive of the following universal conditional statement? ∀m ∈ R: if m>4 then m2>16 A ∀m ∈ R: if m2>=16 then m >= 4 B ∀m ∈ R: if m