HW1 PB21111710

2.1a

1.英文字母a-z,A-Z;

2.数字0-9;

3.空白符：空格，换行，回车，制表符

4.特殊符号：!"#$%&'()*+,-./:;=<?>'[\]^_s{}|~

2.2

1
<key,long> <id,gcd> <sep,'('> <key,long> <id,p> <sep,','> <id,q> <sep,')'> <sep,'{'>
2
    <key,if> <sep,'('> <id,p> <op,&> <id,q> <relation,==> <num,0> <sep,')'>
3
      <key,return> <id,q> <sep,';'>
4
    <key,else>
5
      <key,return> <id,gcd> <sep,'('> <id,q> <sep,','> <id,p> <op,%> <id,q> <sep,')'> <sep,';'>
6
<sep,'}'>

2.3a

以0开头，以0结尾的长度$\ge 2$$\ge2$的01串。

2.4h

所有0的后面只能有0或1个1，所以应该有$(0|01{)}^{\ast }$$(0|01)^*$的格式，在第一个0之前可以有任意多个1，所以正规式为

$1^{\ast }(0|01{)}^{\ast }$$1^*(0|01)^*$

2.7c

NFA如下所示：

状态转换序列：

init->1->2->4->6->7->8->9->10->

2->4->6->7->8->9->8->9->10->

2->4->6->7->8->9->10->11->finish

2.15

题目要求接受大于5的二进制数。我们规定状态的整数为该状态时输入串表示的十进制数。

每输入1位，相当于之前输入的数乘以2加上新的数(0或1)

我们知道，状态为0,1,2时，乘以2加上0或1也无法大于5。

而达到3/4/5时，乘以2就大于5,即达到接收状态(>5)，在这之后任意输入都是>5的接收状态。所以最简DFA如下所示：