Help
Options
Didn't know it?
click below
click below
Knew it?
click below
click below
Don't Know
Remaining cards (0)
Know
retry
shuffle
restart
0:00
Embed Code - If you would like this activity on your web page, copy the script below and paste it into your web page.
Normal Size Small Size show me how
Normal Size Small Size show me how
CSCI 2115
| Question | Answer |
|---|---|
| During an execution, the next state of a Turing machine depends on: I. The current state II. The symbol that is read III. The symbol that is written IV. The direction that the head moves | (b) I and II |
| Which feature of a Turing machine differentiates it from a PDA? (a) Ability to read and modify memory in a single transition. (b) Unbounded amount of memory. (c) Unrestricted ability to access the memory. (d) Unbounded number of states. | (c) Unrestricted ability to access the memory. |
| The program compomnent of a RAM is analgous to (a) The tape of a Turing machine (b) The finite state control of a Turing machine (c) The current state of a Turing machine (d) The accept and reject states of a Turing machine | (b) The finite state control of a Turing machine |
| Consider the problem of determining whether a list is in sorted order. Which of the following applies? I. This problem is in P. II. This problem is in NP. III. This problem is in PSPACE. | (e) I, II, and III |
| Suppose you had a problem whose solution could be verified in polynomial time. Which of the following always applies? I. This problem is in P. II. This problem is in NP. III. This problem is in PSPACE. | (d) II and III |
| Suppose you proved that there was no polynomial time algorithm that could solve SAT. What could you conclude? (a) P = NP (b) P C NP (c) We cannot conclude anything. | (b) P C NP |
| During a transition of a TM, what is the order of operations? I. Move head II. Read symbol III. Select transition IV. Write symbol | (b) II, III, IV, I |
| Suppose that TM M only uses a constant amount of tape in its computation. What can you conclude about the language decided by M? The language can be recognized by a DFA. The language can be recognized by a DPDA. The language can be recognized by | All of these |
| The difference between a cell on the tape of the Turing Machine and the register of a RAM is (a) They store symbols from different alphabets (b) The register has an infinite range and the cell has a finite range. | (b) The register has an infinite range and the cell has a finite range. |
| The indirect access mode is necessary for a RAM because (a) The amount of input is not known in advance (b) The number of registers that an algorithm needs may depend on the input. (c) The number of instructions executed may depend on the input. | (b) The number of registers that an algorithm needs may depend on the input. |
| The Turing Machine decides which transition to use based on: I. The symbol that it reads II. The state it is in III. The symbol that it writes IV. The direction the head moves | I and II |
| Suppose the Turing Machine is in configuration 𝜎<q>𝜏. After a single transition, which parts of this configuration may be modified? | q, and 𝜏 |
| Which of the following abstract models of computation are equivalent to a Turing Machine? PDA DFA Both of these Neither of these | Neither of these |
| A Random Access Machine computes by Executing registers that store instructions Executing the program on the input tape Performing transitions from one register to another Executing instructions that access registers | Executing instructions that access registers |
| A RAM needs the indirect access mode to ________ Access a register determined at execution time Write to the output tape Load a register with a specific value Read the contents of the input tape | Access a register determined at execution time |
| The number of registers used by a RAM to simulate a TM is proportional to The amount of output performed by the TM The amount of tape used by the TM The amount of state transitions performed by the TM The amount of input performed by the TM | The amount of tape used by the TM |
| The complexity of an algorithm is typically viewed as a function of The size of the input The size of the output The number of lines of code in the algorithm The input contents | The size of the input |
| During a transition of a TM, which of the following MUST change? I. The state II. The contents of the tape III. The position of the head | (e) III |
| Suppose that TM M only moves its head to the right during its computation. What can you conclude about the language decided by M? The language can be recognized by a DFA. The language can be recognized by a DPDA. The language can be recognized by a P | All of these |
| The difference between a Turing Machine (TM) and a RAM is | A TM cannot increment an arbitrarily large number in a single step, but a RAM can. |
| Which of the following problems would require a RAM with the indirect addressing mode? | (d) Determine if the string is a palindrome. |
| Suppose you wanted to show that a problem was not in NP. Which of the following would you need to show? I. Problem cannot be solved in polynomial time by a nondeterministic Turing machine IV. Problem cannot be verified in polynomial time by a determ | |
| Which of the following statements would indicate to you that a given problem may not be in P? (a) The problem is in NP (b) The problem is P-hard (c) The problem is P-complete (d) The problem is NP-hard | (d) The problem is NP-hard |
| Suppose you wanted to show that P = NP. You would need to show that (a) An NP-hard problem could be solved on a deterministic Turing machine. (b) An NP-hard problem could be solved in polynomial time on a deterministic Turing machine | (b) An NP-hard problem could be solved in polynomial time on a deterministic Turing machine |
| The growth of a function is determined by The dominant term The smallest term The number of terms The largest multiplicative constant of a term | The dominant term |
| Which of the following abstract models of computation are equivalent to a Turing Machine? DFA All of these PDA NTM | NTM |
| A complexity class is characterized by | The amount of resources necessary to perform a computation as a function of input size. |
| A problem in the class P? | A problem for which a Deterministic Turing Machine (TM) can find a solution in polynomial time. |
| A problem in the class NP? | Can be decided in polynomial time by a Nondeterministic Turing Machine (NTM)and whose solution can be verified in polynomial time. |
| The grep program takes a regular expression that specifies The commands to grep The file to be searched The format of the file The search pattern | The search pattern |
| Which of the following operations is not available in regular expressions? Repetition Intersection Concatenation Alternation | Intersection |
| A language is A set of operations A set of alphabets A set of strings A set of symbols | A set of strings |
| When a DFA reads a symbol it Transitions from state to final state Transition from state to state Recognizes the language Accepts the string | Transition from state to state |
| Which of the following statements is false? A DFA can reject a string A DFA can accept a string A DFA recognizes a language A DFA accepts a language | A DFA accepts a language |
| The state variable in the DFA pattern stores The next state to transition to The symbol for transitioning into the current state The current state Whether the current state is final | The current state |
| Which of the following methods will have the same implementation regardless of the DFA being implemented? (Assume a nested-switch implementation.) Neither next() nor isFinal() Both next() and isFinal() Only next() Only isFinal() | Only isFinal() |
| Which of the following features may be present in nondeterministic finite automata (NFAs) but not in deterministic finite automata (DFAs)? I. multiple final states II. multiple successor states III. epsilon transitions | II and III |
| An NFA accepts a string if and only if at least one path ends in a final state none of the paths end in a final state there is exactly one path that ends in a final state all paths end in a final state | at least one path ends in a final state |
| The purpose of a scanner is to Transform the program source code into an executable Transform the program source code into machine code Determine if a program source code is correct Transform the program source code into a token stream | Transform the program source code into a token stream |
| The scanner works by using a DFA that Rejects the entire program if none of the tokens are correct. Accepts the entire program only if it is correct. Accepts one token at a time, returning each token. | Accepts one token at a time, returning each token |
| The DFA implementation in a scanner must keep track of ______ the number of correct and incorrect tokens. the current token being scanned. all the correct tokens. the previous token that was accepted. | the current token being scanned |
| Which of the following are equivalent: i) Regular languages ii) Regular Expressions iii) DFAs iv) NFAs v) scanners all of them are equivalent except for v All of these only i, ii, and iii are equivalent | all of them are equivalent except for v |
| How do we show that Regular Languages and Regular Expressions are the same? We created a bijective function between both They're the same by definition We showed that it's true only if the DFA is the same We proved it by contradiction | We created a bijective function between both |
| A Generalized NFA is An NFA that has no epsilon transitions An NFA that can recognize more expressions than just Regular Expressions An NFA that has Regular Expressions as transitions instead of symbols | An NFA that has Regular Expressions as transitions instead of symbols |
| What is not a step in collapsing the GNFA? Select a state q to remove Identify adjacent states and all paths through q Remove q from each path Create simpler transitions by using epsilon transitions | Create simpler transitions by using epsilon transitions |
| When converting an NFA to DFA, the initial state of the DFA corresponds to The initial state of the NFA and all states reachable by epsilon transitions from the initial state The initial state of the NFA and all final (accepting) states | The initial state of the NFA and all states reachable by epsilon transitions from the initial state |
| When converting an NFA to DFA using subset construction, the maximum number of new states that can be created by filling in a single row of the table is The size of the alphabet The number of states in the NFA 2 1 | The size of the alphabet |
| A minimal DFA has The smallest set of final states possible The smallest set of states possible The smallest number of transitions to final state possible The smallest alphabet possible | The smallest set of states possible |
| When minimizing a DFA, the first step is to Divide all states among N equivalence classes where N is the number of states in the original DFA. Divide all states among two equivalence classes | Divide all states among two equivalence classes |
| Suppose L is a regular language and L' is not a regular language. Which of the following statements is always true? L u L' is regular. L' \backslash L is regular. L n L' is regular. None of these | None of these |
| Suppose L and L' are regular languages, which of the following is not true? L'' is regular, where L'' = L n L' L'' is regular, where L'' = L^* L'' is regular, where L'' \subset L L'' is regular, where L'' = L u L' | L'' is regular, where L'' \subset L |
| Suppose you want to show that a language is not regular. Which of the following proof techniques are you most likely to use? Proof by contrapositive Direct proof Proof by induction Proof by contradiction | Proof by contradiction |
| In a context free grammar, the left hand side of a production is a Start symbol Variable (or nonterminal) Derivation Terminal | Variable (or nonterminal) |
| Select the best two terms to complete the following sentence. During a step in a derivation a _____ is used to replace a ____ in the sentential form. Production and Variable Production and Terminal Start symbol and Terminal | Production and Variable |
| A string is in a CFL if... there is an NFA that recognizes the string there is a regular expression that recognizes the string it can be created by a parse tree it can be derived by the context free grammar. | it can be derived by the context free grammar. |
| The leaf nodes of a parse tree are Derivations Terminals Start symbols Variables (or nonterminals) | Terminals |
| The difference between a nondeterministic finite automate (NFA) and a push down automata (PDA) is The NFA always accepts with a final state an the PDA never accepts with a final state. The NFA does not have a stack and the PDA does. | The NFA does not have a stack and the PDA does. |
| Which of the following conditions must hold for a PDA to accept a string, regardless of the mode of acceptance? The stack must be empty and and the automaton must be in a final state. The input must be completely read. | The input must be completely read. |
| A Deterministic Push-Down Automata (DPDA) differs from a PDA in that A DPDA must only have one choice of transition at any point in the computation. A DPDA must use the same alphabet for both its input and stack. | A DPDA must only have one choice of transition at any point in the computation |
| Which of the following things does the parser need to perform its function? I. The input program II. The token stream III. The language grammar IV. The parse tree II and III II, III, and IV I and II I and III | II and III |
| In the LL(1) parsing algorithm the stack is used to store... The current lookahead The input seen so far The current production The current sentential form | The current sentential form |
| What must be true about the predictor table for LL(1) parsers? Productions with the same RHS must have disjoint predictor sets. Productions with the same LHS must have disjoint predictor sets. All productions must have disjoint predictor sets. | Productions with the same LHS must have disjoint predictor sets. |
| To build recursive descent parser, Create a function for each production Create a function for each terminal Create a function for each variable (non-terminal) Create a function for each derivation | Create a function for each variable (non-terminal) |
| What is the differences between the iterative and recursive parsing methods? I. The former uses a loop and the latter recursion II. The former uses a stack and the latter does not III. The former is table driven and the latter is coded by hand | I and III |
| In a recursive descent parser, under what conditions is the lookahead token needed? If there are multiple productions with the same predictor sets If there are multiple productions with the same LHS | If there are multiple productions with the same LHS |
| The Turing Machine decides which transition to use based on: I. The symbol that it reads II. The state it is in III. The symbol that it writes IV. The direction the head moves | I and II |
| Suppose the Turing Machine is in configuration 𝜎<q>𝜏. After a single transition, which parts of this configuration may be modified? 𝜎 and 𝜏 𝜎, q, and 𝜏 q and 𝜏 𝜎 and q | q and 𝜏 |
| Which of the following abstract models of computation are equivalent to a Turing Machine? PDA DFA Both of these Neither of these | Neither of these |
| A Random Access Machine computes by Executing registers that store instructions Executing the program on the input tape Performing transitions from one register to another Executing instructions that access registers | Executing instructions that access registers |
| A RAM needs the indirect access mode to ________ Access a register determined at execution time Write to the output tape Load a register with a specific value Read the contents of the input tape | Access a register determined at execution time |
| The number of registers used by a RAM to simulate a TM is proportional to The amount of output performed by the TM The amount of tape used by the TM The amount of state transitions performed by the TM The amount of input performed by the TM | The amount of tape used by the TM |
| The complexity of an algorithm is typically viewed as a function of The size of the input The size of the output The number of lines of code in the algorithm The input contents | The size of the input |
| The growth of a function is determined by The dominant term The smallest term The number of terms The largest multiplicative constant of a term | The dominant term |
| Which of the following abstract models of computation are equivalent to a Turing Machine? DFA All of these PDA NTM | NTM |
| A complexity class is characterized by The amount of resources necessary to perform a computation as a function of output size. The amount of resources necessary to perform a computation as a function of input size. | The amount of resources necessary to perform a computation as a function of input size. |
| The class P contains Problems that can be solved in deterministic polynomial time. Problems that can be solved in nondeterministic polynomial time. Problems that cannot be solved in deterministic polynomial time. | Problems that can be solved in deterministic polynomial time. |
| The class NP contains Problems that can be solved in deterministic polynomial time. Problems whose solutions can be verified in deterministic polynomial time. Problems whose solutions can be guessed in deterministic polynomial time. | Problems whose solutions can be verified in deterministic polynomial time. |
| Which of the following is NOT required to generate a parser? The grammar that specifies the language The attributes to be associated with symbols The actions to be associated with productions The input to be parsed | The grammar that specifies the language |
| What is the correct order for the following operations? I. Instantiate parser Il. Parse the input III. Instantiate the scanner V. Create the token stream III, IV, I, II I, II, III, IV I, III, IV, II | III, IV, I, II |
| Which of the following operations are used to construct regular expressions? I. Alternation II. Concatenation III. Exclusion IV. Repetition | (c) I, II, and IV |
| Which of the following characteristics are true for regular languages? I. The language must be finite. II. The language can be specified by a regular expression. III. The language can recognized by a deterministic finite automaton. | (c) II and III |
| Which of the following conditions are necessary for a DFA to reject a string? I. The DFA is not in a final state II. The DFA is not in a start state III. The DFA has read the entire string IV. The DFA must perform at least one transition | (b) I and III |
| Which of the following components differs between DFAs and NFAs? (a) Q: The set of states (b) Σ: The alphabet (c) q0: the initial state (d) δ: the transition function (e) F: the set of final states | (d) δ: the transition function |
| Under which of the following conditions will an NFA M accept a string σ? | There is one path such that M ends in a final state after reading σ. There are a finite number of paths such that M ends in a final state after reading σ. There are an infinite number of paths such that M ends in a final state after reading σ. |
| Which of the following statements about scanners are true? I. A scanner returns tokens. II. A scanner accepts or rejects programs. III. A scanner must keep track of all input that it has previously processed. IV. A scanner returns the current token wh | (b) I and IV |
| Which statements are true? I For each regular language L, there are many NFAs that recognize L. II. For each NFA M, there are many regular languages that M recognizes. III. For each regular language L, there are many regular expressions that specify L. | (a) I and III |
| Suppose you were minimizing a DFA that initially had 10 states and the alphabet {0, 1}. At most, how many equivalence classes will be created as a result of the minimization process? (a) 2 (b) 8 (c) 10 (d) 12 (e) 20 | (c) 10 |
| Suppose that you were told that L = L1 ∪ L2 was not a regular language. We can then conclude that (a) L1 and L2 must be nonregular languages (b) L1 or L2 must be nonregular languages (c) L1 or L2 must be regular languages (d) None of the above. | |
| Which of the following methods can be used for showing that a language is nonregular. I. The Pumping Lemma II. Closure properties of regular languages III. Constructing an NFA IV. Constructing a Regular Expression | (b) I and II |
| Which of the following statements are true about parse trees? I. Internal nodes are labeled by variables (nonterminals) II. Internal nodes are labeled by variables (nonterminals) or terminals III. Leaf nodes are labeled by terminals | (b) I and III |
| A Push-Down Automata can recognize I. Regular languages II. Languages that have an LL(k) grammar III. Languages that have an LR(k) grammar IV. Context free languages | (d) I, II, III, and IV |
| What is the purpose of the stack in a top-down (LL(1)) parser? (a) To store the input that has been read by the parser. (b) To store the input that will be read by the parser. (c) To store the derivations that have been performed. | (c) To store the derivations that have been performed. |
| Suppose you had a problem whose solution could be verified in polynomial time. Which of the following always applies? I. This problem is in P. II. This problem is in NP. III. This problem is in PSPACE. | (d) II and III |
| Under which of the following conditions will an NFA M have multiple paths for a given string? I. The NFA has epsilon transitions. II. The NFA has transitions with multiple successor states. (a) I (b) I or II (c) I and II (d) II | (c) II |
| Which of the follow operations are necessary to construct an infinite regular language? (a) Alternation (b) Concatenation (c) Empty string (d) Repetition | (d) Repetition |
| Which of the following statements is false? (a) For every NFA there is a DFA that recognizes the same language. (b) For every DFA there is a regular expression that specifies the language that the DFA recoecognizes | (b) For every DFA there is a regular expression that specifies the language that the DFA recoecognizes |
| Suppose that you were told that L = L1\L2 was regular. We can then conclude that (a) L1 and L2 must be regular (b) L1 must be regular (c) L2 must be regular (d) None of the above. | None of the above |
| Which of the following techniques should be used to show that a language is regular? I. Proof by contradiction II. Direct proof using closure properties III. Direct proof using the pumping lemma IV. Direct proof using construction | (c) II and IV |
| Push-Down Automata (PDAs) I. cannot recognize some regular languages II. may be nondeterministic III. must finish reading the input in order to accept IV. must have a complete transition function | (d) II and III |
| An LL(1) parser selects the next production after (c) Popping a variable from the stack getting a terminal from the scanner. (d) Popping a variable from the stack matching it to a variable from the scanner | (d) Popping a variable from the stack matching it to a variable from the scanner. |
| During a transition of a TM, what is the order of operations? I. Move head II. Read symbol III. Select transition IV. Write symbol (a) II, III, I, IV (b) II, III, IV, I (c) III, II, I, IV (d) III, II, IV, I | (b) II, III, IV, I |
| The indirect access mode is necessary for a RAM because (a) The amount of input is not known in advance (b) The number of registers that an algorithm needs may depend on the input. (c) The number of instructions executed may depend on the input. | (b) The number of registers that an algorithm needs may depend on the input. |
| Suppose you were designing a grammar to recognize the language L = {AnBmC `DmE n : n ≥ 0, m ≥ 0, ` ≥ 0}. At minimum, how many states would your PDA need? (a) 1 state (b) 2 states (c) 3 states (d) 4 states (e) 5 states | (e) 5 states |
| Which regular expression operations are necessary to construct a regular expression for the language of all binary strings of length zero or greater? I. Alternation II. Concatenation III. Repetition | (b) I and III |
| Which of the following set operations is not part of the definition of regular languages? I. Union of two languages II. Concatenation of two languages III. Difference of two languages IV. Intersection of two languages | (d) III and IV |
| Suppose you were told that a DFA M recognized a finite language. What can we conclude? (a) Every state in the DFA can be visited at most once. (b) Every state in the DFA is a final state. (c) The start state in the DFA is a final state. | (a) Every state in the DFA can be visited at most once. |
| Suppose that an NFA M has two different paths through it when reading word w. One of those paths ends at a non-final and the other path ends at a final state. What should the NFA do on reading string w? (a) Reject (b) Accept (c) Crash | (b) Accept |
| Which of the following features differentiates NFAs from DFAs? I. Multiple final states. II. Start state can be a final state. III. Recognition of infinite languages. IV. Incomplete transition function. | (e) IV |
| In a table-based scanner what is used to index into the table? I. Transitions II. Words in the language III. States IV. Symbols (a) I and II (b) I and III (c) II and III (d) II and IV (e) III and IV | (e) III and IV |
| Which of the following statements is true? (a) For every DFA there is exactly one NFA that recognizes the same language. (b) For every NFA there is exactly one regular language that it recognizes. | (d) For every NFA there is exactly one regular language that it recognizes. |
| Suppose that you were told that L1 was not regular and L2 was regular. Which of the following statements must be false? (a) L1 = L2∗ (b) L2 = L1∗ (c) L2 ⊆ L1 (d) L1 ⊆ L2 (e) None of the above. | (a) L1 = L2∗ |
| Which of the following techniques are appropriate for proving that a language is not regular? I. Proof using closure properties II. Proof using construction III. Proof using the pumping lemma | I, III |
| Which of the following features may be present in nondeterministic finite automata (NFAs) but not in deterministic finite automata (DFAs)? I. multiple final states II. multiple successor states III. epsilon transitions | II and III |
| An NFA accepts a string if and only if there is exactly one path that ends in a final state none of the paths end in a final state all paths end in a final state at least one path ends in a final state | at least one path ends in a final state |
| The purpose of a scanner is to Transform the program source code into an executable Determine if a program source code is correct Transform the program source code into machine code Transform the program source code into a token stream | Transform the program source code into a token stream |
| The scanner works by using a DFA that Rejects the entire program if none of the tokens are correct. Accepts the entire program only if it is correct. Accepts one token at a time, returning each token. | Accepts one token at a time, returning each token. |
| The DFA implementation in a scanner must keep track of ______ the previous token that was accepted. the number of correct and incorrect tokens. the current token being scanned. all the correct tokens. | the current token being scanned. |
| Which of the operations in a regular expression indicates that the corresponding language is infinite? Concatenation Alternation Repetition Any of these operations | Repetition |
| Which of features of an NFA are needed to implement the regular expression to NFA construction described in class? Just multiple successor states Both epsilon transition and multiple successor states Just epsilon transitions | Both epsilon transition and multiple successor states |
| Suppose you have an NFA with n states, which may or may not be normalized. In the worst case, how may iterations of the state removal procedure would be required to compute the corresponding regular expression? n - 1 n n - 2 n + 1 | n - 1 |
| When converting an NFA to DFA, the initial state of the DFA corresponds to The initial state of the NFA and all final (accepting) states The initial state of the NFA and all states reachable by epsilon transitions from the initial state | The initial state of the NFA and all states reachable by epsilon transitions from the initial state |
| When converting an NFA to DFA using subset construction, the maximum number of new states that can be created by filling in a single row of the table is The size of the alphabet 1 2 The number of states in the NFA | The size of the alphabet |
| A minimal DFA has The smallest set of final states possible The smallest set of states possible The smallest alphabet possible The smallest number of transitions to final state possible | The smallest set of states possible |
| When minimizing a DFA, the first step is to Divide all states among N equivalence classes where N is the number of states in the original DFA. Divide all states among two or more equivalence classes Divide all states among two equivalence classes | Divide all states among two equivalence classes |
| Suppose you want to show that a language is not regular. Which of the following proof techniques are you most likely to use? Proof by induction Proof by contradiction Direct proof Proof by intimidation | Proof by contradiction |
| In a context free grammar, the left hand side of a production is a Derivation Start symbol Terminal Variable (or nonterminal) | Variable (or nonterminal) |
| Select the best two terms to complete the following sentence. During a step in a derivation a ________ is used to replace a ________ in the sentential form. Variable and Terminal Production and Variable Production and Terminal | Production and Variable |
| The leaf nodes of a parse tree are Terminals Variables (or nonterminals) Derivations Start symbols | Terminals |
| The difference between a nondeterministic finite automate (NFA) and a push down automata (PDA) is The NFA is nondeterministic and the PDA is deterministic The NFA does not have a stack and the PDA does | The NFA does not have a stack and the PDA does |
| Which of the following conditions must hold for a PDA to accept a string, regardless of the mode of acceptance? The input must be completely read. The automaton must be in a final state. | The input must be completely read. |
| A Deterministic Push-Down Automata (DPDA) differs from a PDA in that A DPDA does not have a stack. A DPDA must use the same alphabet for both its input and stack. A DPDA must only have one choice of transition at any point in the computation. | A DPDA must only have one choice of transition at any point in the computation. |
| Which of the following productions corresponds to Pattern 2? S → 'a' S 'b' S → S 'a' S S → SS S → 'a' 'b' | S → 'a' S 'b' |
| The top-level structure of language of palindromes L = {𝛔 ∊ {0,1}* | 𝛔 = 𝛔 r } can be described using which pattern(s)? Pattern 2 Pattern 1 or Pattern 2 Pattern 1 and Pattern 2 Pattern 1 | Pattern 2 |
| Which of the following productions would indicate to you that the corresponding language language can only be recognized with a PDA or DPDA? S → S 'a' S S → 'a' S S → 'a' S 'b' | S → 'a' S 'b' |
| Which of the following things does the parser need to perform its function? I. The input program II. The token stream III. The language grammar IV. The parse tree I and III II, III, and IV II and III I and II | II and III |
| In the LL(1) parsing algorithm the stack is used to store The current lookahead The input seen so far The current production The current sentential form | The current sentential form |
| What must be true about the predictor table? Productions with the same LHS must have disjoint predictor sets. All productions must have different LHS. Productions with the same RHS must have disjoint predictor sets | Productions with the same LHS must have disjoint predictor sets. |
| To build recursive descent parser, Create a function for each derivation Create a function for each terminal Create a function for each production Create a function for each variable (non-terminal) | Create a function for each variable (non-terminal) |
| What are the differences between the iterative and recursive parsing methods? I. The former uses a loop and the latter recursion II. The former uses a stack and the latter does not III. The former is table driven and the latter is coded by hand | I and III |
| In a recursive descent parser, under what conditions is the lookahead token needed? If there are multiple productions with the same predictor sets If there are multiple productions with the same LHS | If there are multiple productions with the same LHS |
| Which of the following is NOT required to generate a parser? The attributes to be associated with symbols The input to be parsed The grammar that specifies the language The actions to be associated with productions | The input to be parsed |
| What is the correct order for the following operations? I. Instantiate parser II. Parse the input III. Instantiate the scanner IV. Create the token stream IV, III, II, I I, II, III, IV I, III, IV, II III, IV, I, II | III, IV, I, II |
| The Turing Machine decides which transition to use based on: I. The symbol that it reads II. The state it is in III. The symbol that it writes IV. The direction the head moves I, II, and III I and II I, II, III, and IV I and III | I, II, III, and IV |
| Which of the following abstract models of computation are equivalent to a Turing Machine? DFA NTM PDA All of these | All of these |
| The Church-Turing Thesis states that... (b) a function is computable if and only if it can be solved without any undecidable problems by a Turing machine (c) a function is computable if and only if it can be computed by a Turing machine | (c) a function is computable if and only if it can be computed by a Turing machine |
| What does the time complexity of an algorithm indicate? It outlines the increase in computational steps required as input size grows It represents the number of steps an algorithm takes, which may stay the same regardless of input size. | It outlines the increase in computational steps required as input size grows |
| Which of the following abstract models of computation are equivalent to a Turing machine? I NFA II DPDA III NTM IV Multiple Tape TM V Single Sided Tape TM (a) I and II (b) III, IV, and V (c) II and III (d) II, III, IV, and V (e) IV and V | (b) III, IV, and V |
| Which of the following best describes a problem in the class P? (b) A problem that can be solved in exponential time regardless of the computation model. (c) A problem for which a deterministic Turing machine can find a solution in polynomial time. | (c) A problem for which a deterministic Turing machine can find a solution in polynomial time. |
| What does the space complexity of an algorithm indicate? (b) It represents the number of steps an algorithm takes, which may stay the same regardless of input size. (c) It measures the algorithm’s memory usage as the input size increases. | (c) It measures the algorithm’s memory usage as the input size increases. |
| Which of the following abstract models of computation are not equivalent to a Turing machine? I NFA II DPDA III NTM IV Multiple Tape TM V Single Sided Tape TM (a) I and II (b) III, IV, and V (c) II and III (d) II, III, IV, and V (e) IV and V | (a) I and II |
| Assuming that P != NP != PSPACE, which of the following statements would be FALSE? (a) P ⊂ NP (b) NP ⊂ PSPACE (c) P ⊂ PSPACE (d) NP ⊂ P | (d) NP ⊂ P |
| An “easy” computational problem requires moderate computational resources (time and space) Such a problem is also called tractable requires a lot of computational resources (time or space) Such a problem is also called intractable | requires moderate computational resources (time and space) Such a problem is also called tractable |
| An “hard” computational problem requires moderate computational resources (time and space) Such a problem is also called tractable requires a lot of computational resources (time or space) Such a problem is also called intractable | requires a lot of computational resources (time or space) Such a problem is also called intractable |
| A problem X is NP-Complete if | • X ∊ NP and • X is NP-Hard |
| Proving NP-Hard | •Identify problem Y that is known to be NP-Hard. •Show that problem Y can be reduced to problem X in polynomial time. •Hence, problem X is also NP-Hard. |
| Proving NP-Complete | •Show that X is in NP by showing that X is polynomial time verifiable. •Show that X is NP-Hard |
| Proving Halting Problem in undecidable | Reduce decidability to halting problem proving it is undecidable (proof by contradiction) |
Created by:
mauri1lawson
Popular Computers sets