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+ϵ)$?

  • 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)

选项的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$,对应

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

所以整体的正则表达式为

不难看出下式与上式等价

所以选择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,

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$
  • $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]

第二项从$S_0$接收$0$,无法确定下一步的状态;第三项有$\epsilon$;第四项有无限个状态;所以选择第一项。

Question 12

Which of the following automata are NFAs?

[Check all that apply]

注意NFA是可能有$\epsilon-$移动,所以第一项是NFA;第二项有多个转移,所以也是NFA;第三项有$\epsilon$,所以也是NFA;最后一项有无限多个状态,所以不是NFA。

本文标题:Stanford Compiler Quiz 1

文章作者:Doraemonzzz

发布时间:2020年09月06日 - 17:33:00

最后更新:2020年09月06日 - 21:19:35

原始链接:http://doraemonzzz.com/2020/09/06/Stanford Compiler Quiz 1/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

//