编译原理作业及answer

1.  构造正规式1(0|1)*101相应的DFA.

2.  将图4 16确定化：

[讲义  图4 16]

3  把图4 17的最小化：

[讲义 图4 17]

4  构造一个DFA，它接收Σ={0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边。并给出该语言的正规式。

参

1．解：

                  0,1

                1           1           0            1

    Y

确定化

                    0           1

                1           1           0            1

    D

                                  0                   0

2．解：

                                                      0,1

                         0                  0,1

                                   C                    F

         0

                                  0

                 1

         1

                          1        E         1

                                               0

                        0

3．解：

初始分划得Π0：终态组{0}，非终态组{1,2,3,4,5}

对非终态组进行审查：

{1,2,3,4,5}a{0,1,3,5}

而{0,1,3,5}既不属于{0}，也不属于{1,2,3,4,5}

∵{4} a{0}，所以得新分划

          Π1：{0}，{4}，{1,2,3,5}

对{1,2,3,5}进行审查：

∵{1,5} b{4}

  {2,3} b{1,2,3,5}，故得新分划

          Π2：{0}，{4}，{1, 5}，{2,3}

{1, 5} a{1, 5}

{2,3} a{1,3}，故状态2和状态3不等价，得新分划

          Π3：{0}，{2}，{3}，{4}，{1, 5}

这是最后分划了

最小DFA：

                                                            a

                           b                b

    0

                                             b

          a              a    a

                   b

                  b

                                a

4．构造一个DFA，它接受Σ＝{0,1}上所有满足如下条件的字符串：每个1都有0直接跟在右边，并写出相应的正规式和正规文法。

解：按题意相应的正规表达式是0*(0 | 10)*0*或0*( 100*)*0*

构造相应的DFA，首先构造NFA为

                      0             0              0

ε            ε             ε            ε    Y

                                  1       0

用子集法确定化

                                  0

    1       0    2

               1        1         0

                          1

    4

                          0

可最小化，终态组为{1,2,4}，非终态组为{3}，{1,2,4}0{1,2,4}，{1,2,4}1{3}，所以1,2,4为等价状态，可合并。

        0

                        1

    1,2,4

                        0