How many distinct strings are in the language of the regular expression:
$(0 + 1 + \epsilon)(0 + 1 + \epsilon)(0 + 1 + \epsilon)(0 + 1 + \epsilon)$
?

Consider the string $abbbaacc$. Which of the following lexical specifications produces the tokenization $ab\;/\;bb\;/\;a\;/\;acc$ ?
[Check all that apply]

Using the lexical specification below, how is the string "dictatorial" tokenized?

dict (1)
dictator (2)
[a-z]* (3)
dictatorial (4)

Which of the following regular expressions generate the same language as the one recognized by this NFA?
[Check all that apply]

Let $S_i$ be the string consisting of $i$ 0's follwed by $2i$ 1's. Define the language $L_n = \{ S_i | 1 \leq i \leq n \}$. For example,

$L_3 = \{\, 011,\, 001111,\, 000111111\; \}$.

For any given $n$, what is the smallest number of states needed for a DFA that recognizes $L_n$?

The language of the regular expresion (abab)* is equivalent to the language of which of the following regular expressions?
[Check all that apply]

What is the minimum number of states a DFA recognizing the language of $a(bc)^*d$ can have?

Given the following lexical specification:

a(ba)*
b*(ab)*
abd
d+

Which of the following statements is true?
[Check all that apply]

Given the following lexical specification:

(00)*
01+
10+

Which strings are NOT successfully processed by this specification?
[Check all that apply]

For any language $L$, the complement of the language (usually written $L'$) is defined as the language
that consists of all the strings that are NOT in $L$. That is,

$L' = \Sigma^* - L$

It turns out that the complement of any regular language is also a regular language.

Which of the following regular expressions define a language that is the complement of the language defined by the
regular expression: $1(01)^*$?
[Check all that apply]

Which of the following automata are DFAs?
[Check all that apply]

Which of the following automata are NFAs?
[Check all that apply]