给出语言L（G)={a2n＋1b2ma2p＋1|n≥0 p≥0 m≥1}正规式及该正规式的DFA。

描述该语言的正规式为：a(aa)*bb(bb)*a(aa)*
   首先从该正规式出发，构造等价的非确定有限自动机，如图3-31所示。
   
   得到了非确定有限自动机后，下面用子集法进行确定化，如表3-18所示。
表3-18　　对a(aa)*bb(bb)*a(aa)*非确定有限自动机进行确定化
状态子集 a b初态集{X}的ε闭包：
{X} Next({X},a)：
{0,6,1} Next({X},b)：
Ф{0,6,1} Next({0,6,1},a)：
{9} Next({0,6,1},b)：
{2}{9} Next({9},a)：
{6,1} Next({9},b)：
Ф{2} Next({2},a)：
Ф Next({2},b)：
{3,7,4}{6,1} Next({6,1},a)：
{9} Next({6,1},b)：
{2}{3,7,4} Next({3,7,4},a)：
{5,8,Y} Next({3,7,4},b)：
{10}{5,8,Y} Next({5,8,Y},a)：
{11} Next({5,8,Y},b)：
Ф{10} Next({10},a)：
Ф Next({10},b)：
{7,4}{11} Next({11},a)：
{8,Y} Next({11},b)：
Ф{7,4} Next({7,4},a)：
{5,8,Y} Next({7,4},b)：
{10}{8,Y} Next({8,Y},a)：
{11} Next({8,Y},b)：
Ф
   将状态子集重新命名，得到下面的状态转换矩阵，如表3—19所示。
表3—19 得到的a(aa)*bb(bb)*a(aa)*状态转换矩阵
状态 a b0初态 1 -1 2 32 4 -3 - 54 2 35 6 76终态 8 -7 - 98 10 -9 6 710终态 8 -
   左上角{X}的ε闭包所对应的状态是确定有限自动机的初始状态，含有原非确定有限自动机终止状态Y的状态子集所对应的状态是确定有限自动机的终止状态。就得到如图3—32所示的正规式a(aa)*b(bb)*a(aa)*的未化简的确定有限自动机。
   
   对确定有限自动机进行最小化：
   首先，状态集划分为非终态集{0,1,2,3,4,5,7,8,9}和终态集{6,10}。
   考察集合{6,10}，看是否需要划分为不同的集合。在该集合中，状态6,10接受a都到达8，所以不能再分。
   考察集合{0,1,2,3,4,5,7,8,9}，看{0,1,2,3,4,5,7,8,9}是否可以进一步划分。状态0，2，8只能接受字符a，所以应该将{0,1,2,3,4,5,7,8,9}分解为{0,2,8}和{1,3,4,5,7,9}。于是得到新的划分：
   {0,2,8}，{1,3,4,5,7,9}，{6,10}
   对于集合{1,3,4，5,7,9}，状态3，7只能接受b，所以将集合{1,3,4,5,7,9}分解为{3,7}和{1,4,5,9}，得到新的划分：
   {0,2,8}，{3,7}，{1,4,5,9}，{6,10}
   对于集合{0,2,8}，状态0接受字符a到状态1，状态2接受字符a到状态4，状态8接受字符a到状态10，状态1，4属于当前同一集合，而状态10属于另一集合，所以应该将{0,2,8}分解为{0,2}和{8}。于是得到新的划分：
   {0,2}，{3,7}，{1,4,5,9}，  {6,10}，  {8}
   对于集合{1,4,5,9}，状态1，4接受字符a到状态2，状态5，9接受字符a到状态6，状态2，6不属于当前同一集合，所以应该将{1,4,5,9}分解为{1,4}和{5,9}。于是得到新的划分：
   {0,2}，{3,7}，{1,4}，{5,9}，{6,10}，{8}
   采用同样的方法，经过考察后发现其中的每个状态子集都不可能进一步划分了，这样就得到了最后的划分。对每个状态子集，选一个状态作为代表，删除其余状态，把导入被删除状态的边改成导向所选择的代表状态，得到如图3-33所示的正规式a(aa)*bb(bb)*a(aa)*的化简后的确定有限自动机。