https://www.edx.org/course/compilers

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

#### Question 1

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

• 31
• 12
• 16
• 32
• 64
• 81

#### Question 2

Consider the string $abbbaacc$. Which of the following lexical specifications produces the tokenization $ab/bb/a/acc$ ?

[Check all that apply]

• $a(b+c^{\star}),b^+$
• $ab,b^+,ac^{\star}$
• $c^{\star},b^+,ab,ac^{\star}$
• $b^+,ab^{\star},ac^{\star}$

#### Question 3

Using the lexical specification below, what sequence of the rules is used to tokenize the string “dictatorial”?

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

#### Question 4

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

• $(000)^{\star}(01)^+$
• $0(000)^{\star}1(01)^{\star}$
• $(000)^{\star}(10)^+$
• $0(000)^{\star}(01)^{\star}$
• $0(00)^{\star}(10)^{\star}$

#### Question 5

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,

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

• $3n+1$
• $2n$
• $3n$
• $3n+2$
• $3(n+1)$
• $n^2+2n-2$

#### Question 6

The language of the regular expresion $(abab)^{\star}$ is equivalent to the language of which of the following regular expressions?

[Check all that apply]

• $(aba\,(baba)^\star\,b) + \epsilon$
• $(ab\,(abab)^\star\,ab) + \epsilon$
• $(a\,(ba)^{\star}\,b) + \epsilon$
• $(ab)^{\star}$

#### Question 7

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

• $4$
• $3$
• $6$
• $8$

$4$个状态，分别记为$S_i$，$S_1$为起始状态，$S_4$为接收状态。

• $S_1\to^{a} S_2$
• $S_2\to^{d}S_4,S_2\to ^{b}S_3$
• $S_3\to ^c S_2$

#### Question 8

Given the following lexical specification:

• $a(ba)^{\star}$
• $b^{\star}(ab)^{\star}$
• $abd$
• $d^+$

Which of the following statements is true?

[Check all that apply]

• $babad$ will be tokenized as: $bab/a/d$
• $ababdddd$ will be tokenized as:$abab/dddd$
• $dddabbabab$ will be tokenized as:$ddd\;/\;a\;/\;bbabab$
• $ababddababa$ will be tokenized as: $ab\;/\;abd\;/\;d\;/\;ababa$

#### Question 9

Given the following lexical specification:

• $(00)^{\star}$
• $01^+$
• $10^+$

Which strings are NOT successfully processed by this specification?

[Check all that apply]

• $0111110$
• $01100110$
• $0001101$
• $01100100$

#### Question 10

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,

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)^{\star}$?

[Check all that apply]

• $(10)^\star + ((10)^\star 0(0 + 1)^\star ) + (1(01)^\star 1(0 + 1)^\star )$
• $\epsilon + (0(0 + 1)^\star) + ((0 + 1)^\star0) + \big((0 + 1)^\star(00 + 11)(0 + 1)^\star\big)$
• $(0 + \epsilon)\big((1 + \epsilon)(0 + \epsilon)\big)^\star$
• $(10)^\star$

#### Question 11

Which of the following automata are DFAs?

[Check all that apply]

#### Question 12

Which of the following automata are NFAs?

[Check all that apply]

//