Kleene's algorithm: Difference between revisions

Revision as of 20:10, 31 May 2014

Revision as of 20:15, 31 May 2014

Line 219:

| ''R''{{su|p=2|b=''00''}}    

| | = ''R''{{su|p=1|b=''02''}} (''R''{{su|p=1|b=''22''}})^* ''R''{{su|p=1|b=''20''}} | ''R''{{su|p=1|b=''00''}}    

| | = ''a''^*''b''^*''ba''

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | ∅

Line 227:

| ''R''{{su|p=2|b=''01''}}

| | = ''R''{{su|p=1|b=''02''}} (''R''{{su|p=1|b=''22''}})^* ''R''{{su|p=1|b=''21''}} | ''R''{{su|p=1|b=''01''}}

| | = ''a''^*''b''^*''ba''

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | (''ba'' | ε''b'')''b''^*

| | | ''a''^* ''b''^* ''b''

| | =

Line 235:

| ''R''{{su|p=2|b=''02''}}

| | = ''R''{{su|p=1|b=''02''}} (''R''{{su|p=1|b=''22''}})^* ''R''{{su|p=1|b=''22''}} | ''R''{{su|p=1|b=''02''}}

| | = ''a''^*''b''^*''ba''

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | ((''a''|''b'')''b''^*''a'' | ε)

| | | ''a''^* ''b''^* ''ba''

| | =

Line 243:

| ''R''{{su|p=2|b=''10''}}

| | = ''R''{{su|p=1|b=''12''}} (''R''{{su|p=1|b=''22''}})^* ''R''{{su|p=1|b=''20''}} | ''R''{{su|p=1|b=''10''}}

| | = (''b''^* | ε)''a''

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | ∅

Line 251:

| ''R''{{su|p=2|b=''11''}}

| | = ''R''{{su|p=1|b=''12''}} (''R''{{su|p=1|b=''22''}})^* ''R''{{su|p=1|b=''21''}} | ''R''{{su|p=1|b=''11''}}

| | = (''b''^* | ε)''a''

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | (''ba'' | ε''b'')''b''^*

| | | ''b''^*

| | =

Line 259:

| ''R''{{su|p=2|b=''12''}}

| | = ''R''{{su|p=1|b=''12''}} (''R''{{su|p=1|b=''22''}})^* ''R''{{su|p=1|b=''22''}} | ''R''{{su|p=1|b=''12''}}

| | = (''b''^* | ε)''a''

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | ((''a''|''b'')''b''^*''a'' | ε)

| | | ''b''^* ''a''

| | =

Line 267:

| ''R''{{su|p=2|b=''20''}}

| | = ''R''{{su|p=1|b=''22''}} (''R''{{su|p=1|b=''22''}})^* ''R''{{su|p=1|b=''20''}} | ''R''{{su|p=1|b=''20''}}

| | = ((''a'' | ''b'')''b''^*''a'' | ε)

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | ∅

Line 275:

| ''R''{{su|p=2|b=''21''}}

| | = ''R''{{su|p=1|b=''22''}} (''R''{{su|p=1|b=''22''}})^* ''R''{{su|p=1|b=''21''}} | ''R''{{su|p=1|b=''21''}}

| | = ((''a'' | ''b'')''b''^*''a'' | ε)

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | (''ba'' | ε''b'')''b''^*

| | | (''a'' | ''b'') ''b''^*

| | =

Line 283:

| ''R''{{su|p=2|b=''22''}}

| | = ''R''{{su|p=1|b=''22''}} (''R''{{su|p=1|b=''22''}})^* ''R''{{su|p=1|b=''22''}} | ''R''{{su|p=1|b=''22''}}

| | = ((''a'' | ''b'')''b''^*''a'' | ε)

| | ((''a''|''b'')''b''^*''a'' | ε)^*

| | ((''a''|''b'')''b''^*''a'' | ε)

| | | (''a'' | ''b'') ''b''^* ''a'' | ε

| | =