CSCI-2115 – Fall – 2021 Module 2 Quiz
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
CSCI-2115 – Fall – 2021
Module 2 Quiz
1. 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) 6 : the transition function (e) F : the set of final states
2. Under which of the following conditions will an NFA M accept a string σ?
I. There is no path such that M ends in a final state after reading σ .
II. There is one path such that M ends in a final state after reading σ .
III. There are a finite number of paths such that M ends in a final state after reading σ .
IV. There are an infinite number of paths such that M ends in a final state after reading σ .
(a) I
(b) II
(c) II or III
(d) II, III or IV (e) II or IV
3. 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 when there is no transition from the current state.
(c) I and III
(c) I and IV
(c) 1, II, and IV
(c) II and III
(c) II and IV
4. Which of the following 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.
IV. For each regular expression R, there are many regular languages that R can specify.
(c) I and III
(c) I and IV
(c) 1, II, and IV
(c) II and III
(c) II and IV
5. Suppose NFA M(R) recognizes language R and NFA M(s) recognizes language s. Suppose that each of the NFAs had only one final state qF and initial state q0 . What language L does the following NFA recognize?
(a) L = R(R*)s
(b) L = Rs
(c) L = R * s
(d) L = R * us
6. Suppose a DFA M was constructed from the following NFA using standard subset construction as discussed in class. What would be the initial state of M?
(a) q0
(b) {q0 }
(c) {q0.q1 }
(d) {q0.q1.q2 }
(e) {q0.q1.q3 }
7. 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
8. Suppose that you were told that L = L1 u 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.
9. 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
(a) I
(b) I and II
(c) II
(d) II, III, and IV (e) I, II, III, and IV
10. Consider the following Antlr script:
grammar Scheme;
scheme : (NUM | VAR | LPAREN | RPAREN | WS)* ;
NUM : ’- ’?[0- 9]+ ;
VAR : [A-Za- z_ ][A-Za- z0- 9_ ]* ;
LPAREN : ’(’ ;
RPAREN : ’)’ ;
WS : [ \t\r\n] -> skip;
Which of the inputs has tokens that would not be accepted by the scanner generated from the above script? (Hint: Break up each of the following inputs into the tokens as specified in the script.)
(a) (Alice 42 -10)
(b) (Alice 42Bob 10)
(c) (Alice 42 -Bob)
(d) (Alice42 -10Bob)
11. [5 Marks] Using the definition of regular languages, show that the language of all binary strings ending in 11 is regular. E.g., 011011, 111, 11, 00011 are all in the language. Recall, that the binary alphabet is Σ = {0.1}.
2023-02-02