Stanford Compiler Quiz 1

课程主页：

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

课程视频：

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

这次回顾Quiz 1。

Question 1

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

注意此题不能使用乘法原理，因为

$00\epsilon0=000\epsilon$

正确的计算方法应该是根据字符串长度：

$\sum_{i=0}^4 2^i=2^5-1=31$

所以选择第一项。

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

选项中的词法规则是按照优先级排列的，所以前三项都可以匹配出上述符号，但是最后一项的匹配结果为

$abbb/a/acc$

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)

选项的1,2,3,4是指优先级，3,4都可以匹配该字符串，但是3的优先级高，所以选3

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

题目中应该默认$S_0$为起点，那么进入$S_3$的$0$数量为$3k+1$，对应

$0(000)^{\star}$

然后$S_3$到$S_4$的对应的正则表达式为

$1(01)^{\star}$

所以整体的正则表达式为

$0(000)^{\star}1(01)^{\star}$

不难看出下式与上式等价

$(000)^{\star}(01)^+$

所以选择1,2

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,

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

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$

这题给出的标准答案是$3n+1$，解释是需要数$0$和$1$的数量，包括起始点，所以一共$3n+1$。

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$个状态，分别记为$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$

第一项：

$011111/0$

第二项：

$011/00/110$

第三项：

$00/011/01$

第四项：

$011/00/100$

注意第一第二项的最后一部分是无法匹配的，所以选择第一第二项。

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,

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

注意

$1(01)^{\star}=1,101,10101,\ldots$

选择第一第二项。

这个验证起来太花时间，过程从略。