2.22.2024
Question 1: What is the form of the rule that would be useful when equal counts of terminals a and b are needed and a’s must come before b’s in a CFL? Assume R is a variable.
(3 points)
A. $R \rightarrow Rba$
B. $R \rightarrow bRa$
C. $R \rightarrow aRb$
D. $R \rightarrow \epsilon$
E. $R \rightarrow baR$
Answer
C. $R \rightarrow aRb$Question 2: Consider a grammar with the 4 rules below and start variable E:
$E\rightarrow E$$+$$E|E$$^{*}$$E|$$($$E$$)$$|$$a$
Which of the following words could not be generated by this grammar? (terminals in blue)
(3 points)
A. $(a+a)+a$
B. $(a+a)^{*}a$
C. $(a+a)a$
D. $a^{*}(a+a)$
E. none of the above
Answer
C. $(a+a)a$Question 3: How many DFAs can be constructed to recognize all the words of the language $\{w|w=0^{n}1^{n}0^{n}\} \text{ for } n > 0\}$, assuming $\Sigma = \{0, 1\}$?
(3 points)
A. one
B. an infinite number
C. zero
D. three
E. none of the above