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 nal 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)  {q0q1 }

(d)  {q0q1q2 }

(e)  {q0q1q3 }

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}.