CREATE TEST

ERASED TEST, YOU MAY BE INTERESTED ON grammars and more

COMMENTS	STATISTICS	RECORDS

TAKE THE TEST

Title of test: grammars and more Description: grammars, FSM and Author: noob saibot Other tests from this author Creation Date: 30/08/2024 Category: Computers Number of questions: 25

Share the Test:

New Comment

No comments about this test.

Content:

The grammar G = ({S, A, B}, {0, 1}, P, S), where P is given by the production rules S → 0AB | 1BA A → 0AS | 1A | ε B → 0B | 1BS | ε generates a language that HINT: STUDY THE DIFFERENCE BETWEEN CONTEXT FREE AND REGEX (A) belongs to the class Regular. (B) contains the empty string ε. (C) can be accepted by a pushdown automaton. (D) can be denoted by a regular expression. (E) is equal to the set of strings { x ∈ {0, 1}* | x ​​has an equal number of zeros (0) and ones (1) }. Considering the languages ​​L = { 0n1n2i | n ≥ 0 and i ≥ 0 } and M = { 0i1n2n | n ≥ 0 and i ≥ 0 }, it can be stated that HINT: LEARN THE DIFFERENCES BTW CONTEXT-FREE AND REGEX (A) the language L ∪ M can be generated by a context-free grammar. (B) the language M can be generated by a regular grammar. (C) the language L can be accepted by a deterministic finite automaton. (D) the language L ∩ M belongs to the class of context-free languages. (E) the language M can be denoted by a regular expression. In a programming language source text, the compiler identifies the grammatical function of words, verifies the grammatical structure of commands and their meanings. The architectural components of a compiler that perform these activities are, respectively, (A) lexical analyzer, semantic analyzer, intermediate code optimizer. (B) lexical analyzer, syntactic analyzer, semantic analyzer. (C) syntactic analyzer, code generator, semantic analyzer. (D) semantic analyzer, intermediate code generator, intermediate code optimizer. (E) syntactic analyzer, semantic analyzer, code generator. What type of finite state machine is shown in the figure? (A) Asynchronous Mealy (B) Synchronous Mealy (C) Moore D) MacGyver (E) Turing. Regarding the syntax-directed translation technique, it is correct to state that: remember the nakamura principle A) A syntax-directed definition is a context-free grammar with attributes and rules. The attributes are associated with the productions, and the rules with the terminal and non-terminal symbols of the grammar. B) A syntax-directed definition is called an S-attributed definition when only inherited attributes are involved. C) The semantic rules are only applied after the complete construction of the syntax tree by the compiler's parser. D) Dependency graphs are used to determine an evaluation order for the instances of the attributes of a derivation tree. E) Since “S” is a symbol of the grammar present in a derivation tree, a synthesized attribute is computed through the values ​​of the attributes of the sibling nodes or the parent node of “S”. An algorithm has complexity O(3m³ + 2mn² + n² + 10m + m²). A simplified way to represent the complexity of this algorithm is: WARNING: DUBIOUS A) O(m³ + mn²). B) O(m³). C) O(m²). D) O(mn²). E) O(m³+ n²). The running time T(n) of an algorithm, where n is the input size, is given by the recurrence equation T(n) = 8T(n/2)+q*n if n > 1. Since T(1) = p, and that p and q are arbitrary constants, the complexity of the algorithm is: A) O(n). B) O(n log n). C) O(n²). D) O(n³). E) O(n^n). Regarding the design of algorithms, relate Column 1 to Column 2. Column 1 1. Trial and error. 2. Divide and conquer. 3. Greedy. 4. Approximate. 5. Heuristic. Column 2 ( ) The algorithm decomposes the process into a finite number of partial subtasks that must be explored exhaustively. ( ) The algorithm divides the problem to be solved into smaller parts, finds solutions for the parts and then combines the solutions obtained into a global solution. ( ) The algorithm builds an optimal solution in stages. At each step, after selecting an element from the input (the best), it decides whether it is viable (in which case it will become part of the solution) or not. After a sequence of decisions, a solution to the problem is reached. ( ) The algorithm generates solutions whose result is within a limit for the ratio between the optimal solution and the one produced by the algorithm. ( ) The algorithm may produce a good result, or even obtain an optimal solution, but it may also produce no solution at all or a solution far from the optimal solution. The correct order for filling in the parentheses, from top to bottom, is: A) 1 – 2 – 3 – 4 – 5. B) 2 – 3 – 4 – 5 – 1. C) 3 – 4 – 5 – 1 – 2. D) 4 – 5 – 1 – 2 – 3. E) 5 – 1 – 2 – 3 – 4. Page replacement algorithms are important in operating systems that use virtual memory techniques. In general, a page replacement algorithm is chosen that results in a lower page fault rate. However, some page replacement algorithms present Belady's anomaly. This anomaly is characterized by the fact that the number of page faults increases as the Belady's anomaly -> Belaaaaaaaaaady's aaaaaaaaaanomaly A) execution time increases. B) number of allocated pages increases. C) number of unallocated pages increases. D) retention time of allocated pages increases. E) number of times allocated pages are accessed. The main task of a lexical analyzer is to read the characters from the source program input, group them into lexemes and generate a sequence of tokens that will be sent to the syntactic analyzer. Regarding the lexical analyzer, analyze the following assertions: I. In addition to identifying lexemes, other tasks can be performed by this analyzer, such as: removing comments and white spaces and associating error messages with lines of the source program. II. Token is the basic unit of the source text. It can be represented by three pieces of information: the token class, which represents the type of token recognized, the token value, which is the text of the recognized lexeme and the position that indicates the place in the source text (line and column) where the token occurred. III. Regular expressions and lexical analyzer generators are notations used to specify lexeme patterns. IV. In lexical analysis, an intermediate representation of the tree type is created. This presents the grammatical structure of the sequence of tokens. Which are correct? A) Only I. B) Only II. C) Only IV. D) Only I and II. E) Only III and IV. Analyze the following assertions about automata and languages: I. Deterministic finite automata and non-deterministic finite automata accept the same set of languages. II. If L is a context-free language, there exists a deterministic two-stack automaton that recognizes L. III. Every recursively enumerable language is also a recursive language. Which are correct? HINT: CONTEXT-FREE LANGUAGES ARE SUIED FOR PUSHDOWN AUTOMATA WATCH OUT: The relationship between recursively enumerable languages (also known as Turing-recognizable languages) and recursive languages (also known as Turing-decidable languages) is different. the former (recognisable) won't halt is a weird string is entered. the latter will (recognisable and decidable). A) Only I. B) Only II. C) Only I and II. D) Only I and III. E) Only II and III. Suppose that instead of splitting into two parts, we create a version of merge-sort that splits the input into four parts, sorts each quarter-part, and finally combines these four parts using an O(n) procedure. The recurrence equation that describes the running time of this algorithm is: A) T(n) = 4*T(n/4) + O(n) B) T(n) = 4*T(n/2) + 2*O(n) C) T(n) = T(n/4) + 4*O(n) D) T(n) = 4*T(n/4) + 4*O(n) E) T(n) = T(n/4) + O(n). Regarding the wavelet transform for digital image processing, it is correct to state that: ??? A) It is an algorithm that produces classification of objects in the image. B) It is a technique that allows the processing of the image in multiresolution. C) It is a technique capable of extracting frequencies from the image without their temporal location. D) It is a technique that allows the generation of higher resolution images. E) It is an algorithm capable of understanding granular information in digital images. Consider the grammar G described below: set of terminals {a,c}, set of non-terminals {S,A}, initial symbol S and containing the productions below: S -> AcS S -> A A -> aAa A -> a Also consider the finite automaton A over the alphabet {a,c}, with set of states {q0,q1,q2} — of which q0 is initial and q1 is final — and with state transition function determined by the following graph: Let L(G) be the language generated by grammar G and L(A) be the language recognized by automaton A, select the correct alternative. A) L(G) is regular and L(A) is a proper subset of L(G). B) L(G) is not regular and L(A) is a proper subset of L(G). C) L(A) = L(G). D) L(G) is regular and L(G) is a proper subset of L(A). E) L(G) is not regular and L(G) is a proper subset of L(A). The syntactic analysis phase of a compiler can be implemented through context-free grammar parsers, with bottom-up or top-down strategies. Consider the grammar with five productions below, where the symbols S and A are non-terminal, the first being the initial non-terminal symbol of the grammar, and the others being terminal symbols: Analyze the following assertions: I. The grammar is recognized by an LL(1) predictive parser, since the grammar characteristics do not inhibit the construction of the recognition table. II. This grammar is not recognized by an LR(0) parser, since there is a stack-reduce conflict in the state that contains the following LR(0) items “S -> bd . a”, and “A → d”. III. The grammar is recognized by an SLR(1) parser, since it resolves the LR(0) stack-reduce conflict. IV. The grammar is LR(1). Which are correct? A) Only I. B) Only II. C) Only II and III. D) Only II and IV. E) I, II, III and IV. To measure the cost of executing an algorithm, it is common to define a complexity function f, where f(n) is the measure of time required to execute an algorithm for a problem of size n. Consider the following statements about complexity functions: I. If f(n) is a measure of the amount of time required to execute an algorithm on a problem of size n, then f is called the time complexity function. II. If f(n) is a measure of the amount of memory required to execute an algorithm of size n, then f is called the space complexity function. III. Time complexity does not represent time directly, but is estimated by the number of times a given relevant operation is executed. Which are correct? A) Only I. B) Only II. C) Only III. D) Only I and II. E) I, II, and III. A compression algorithm takes as input a sequence of bits (bitstream) and converts it into another bitstream, representing the compressed input. Analyze the following assertions about the Huffman compression technique: I. It is more efficient for compressing text files than the run-length encoding (RLE) technique. II. The technique requires as input a bitstream and a set of prefix-free codes, which associate symbols with a set of bits. III. The resulting compressed bitstream includes the set of codes used to perform the compression. Which are correct? A) Only I. B) Only II. C) Only III. D) Only I and II E) Only I and III. Edges are explored from the most recently discovered vertex v that still has unexplored edges leading from it. When all edges adjacent to v have been explored, the search moves backwards to explore vertices leading from the vertex from which v was discovered. The process continues until all vertices reachable from the original vertex have been discovered. Which graph algorithm has the strategy described above? A) Topological sort. B) Depth-first search. C) Strongly connected D) Minimum spanning tree. E) Breadth-first search. Consider the syntax-driven translation scheme presented below, in which the grammar productions have been numbered: Select the correct alternative regarding the scheme. A) In production 4, T.val and F.val are synthesized. B) In production 4, T1.val is inherited. C) In production 5, T.val and F.val are inherited. D) In ​​production 2, E.val is synthesized and T.val is inherited. E) In production 2, E1.val is synthesized and T.val is inherited. Consider L1 and L2 as two formal languages ​​over the alphabet Σ = {0,1}, described as follows: L1 = { ww | w ∈ Σ* } L2 = { 0a1b | a>0, b>0, b odd } In the above description, juxtaposition means concatenation of words and Σ* denotes the set of all words over the alphabet Σ. Let A1 be the finite automaton over the alphabet Σ = {0,1} described by the following state transition diagram: Let ACCEPT(A1) be the set of words accepted by A1. In this sense, consider the following statements: I. L1 is a regular language. II. L2 is a context-free language. III. ACCEPT(A1) = { w | w ∈ Σ* and w has an odd number of zeros }. Which are correct? A) Only I. B) Only II. C) Only I and III. D) Only II and III. E) I, II and III. Given the regular grammar (G), determine what is the regular expression (r) such that L (r) = L(G): A) r = (ab)*a B) r = aba* C) r = a*(ba) D) r = (a+b)*a* E) r = (ab) + a. Given the grammar G = (V, 𝛴, P, S ), where P = { S ::= (S) S , S ::=𝜀 }, find the recognizer for the language generated by G. REMEMBER: nested parentheses imply the need for memory, and specifically, a stack is the appropriate data structure to handle this kind of memory requirement. A) Regular Expression. B) Deterministic Finite C) Nondeterministic Finite Automaton. D) Pushdown Automaton. E) None of the above. Regarding the pumping lemma for regular languages, analyze the following assertions: I. If a language is Regular, then it is accepted by a Deterministic Finite Automaton which has a finite and predefined number of n states. II. If the automaton recognizes an input w of length greater than or equal to n, the automaton must assume some state q more than once, so there is a cycle in the program function that passes through q. (HINT: look up teh pidgeonhole principle for input greater than the n° of states). III. The input w can be divided into 3 subwords w = xyz such that |xy| <= n, |y| >= 1 and where y is the part of w recognized by the cycle in the program function. IV. The Pumping Lemma cannot be used to prove that a given language is Non-Regular. Which are correct? HINT: regular language -> compatible with a DFA (deterministic finite automaton). A) Only I and II. B) Only III and IV. C) Only I, II and III. D) Only II, III and IV. E) I, II, III and IV. The execution time of a recursive algorithm is analyzed by: REMEMBER: recursion: recurrence + restrictions A) A recurrence equation that defines mathematical restrictions that the execution time of the algorithm must follow. B) A logarithm that transforms into an equality of powers of the same base at each of the recursive calls. C) A randomization function that defines the probabilities over a sample space, defined as the set of all possible results of the execution of each call of the algorithm. D) A random variable that defines a function that maps the result of the execution of each call of the algorithm to a sample space of real numbers. E) Summations. The following algorithms represent the three walks for binary trees. walk(binary) if binary.left 6= NULL then walk(binary.left) write binary.value if binary.right 6= NULL then walk(binary.right) walk(binary) write binary.data if binary.left 6= NULL then walk(binary.left) if binary.right 6= NULL then walk(binary.right) walk(binary) if binary.left 6= NULL then walk(binary.left) if binary.right 6= NULL then walk(binary.right) write binary.value Select the alternative that contains the names of the 3 walks, respectively. a) pre-order, post-order, in-order b) pre-order, in-order, post-order c) post-order, pre-order, in-order d) in-order, pre-order, post-order e) in-order, post-order, pre-order.

Report abuse