Kleene's algorithm: Difference between revisions

Revision as of 19:19, 31 May 2014

Revision as of 19:31, 31 May 2014

Line 29:

Kleene's algorithm computes the initial regular expressions as

{|

{| class=wikitable

|-

| | ''R''{{su|p=-1|b=''00''}}    
| | = ''a'' | ε

| | ''R''{{su|p=-1|b=''01''}} = ''b''

| | ''R''{{su|p=-1|b=''02''}} = ∅

|-

| | ''R''{{su|p=-1|b=''1001''}} = ∅

| | ''R''{{su|p=-1|b=''11''}} = ''b'' | ε

| | ''R''{{su|p=-1|b=''12''}} = ''a''

|-

| | ''R''{{su|p=-1|b=''2002''}} = ∅

| | = ∅

| | ''R''{{su|p=-1|b=''21''}} = ''a'' | ''b''

|-

| | ''R''{{su|p=-1|b=''22''}} = ε

| | ''R''{{su|p=-1|b=''0110''}} = ''b''

| | = ∅

|-

| | ''R''{{su|p=-1|b=''0211''}} = ∅

| | = ''b'' | ε

|-

| | ''R''{{su|p=-1|b=''12''}} = ''a''

| | = ''a''

|-

| ''R''{{su|p=-1|b=''20''}}

| | = ∅

|-

| | ''R''{{su|p=-1|b=''21''}} = ''a'' | ''b''

| | = ''a'' | ''b''

|-

| | ''R''{{su|p=-1|b=''22''}} = ε

| | = ε

|}

Step 0:

{|

{| class=wikitable

|-

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

| | ''R''{{su|p=0|b=''22''}} = ''R''{{su|p=-1|b=''2000''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''0200''}} | ''R''{{su|p=-1|b=''2200''}} = ∅ (''a'' | ε)^* ∅ | ε =  ε 

| | = (''a'' | ε)

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

| | (''a'' | ε)

| | | ''a'' | ε    

| | = ''a''^*

|-

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

| | ''R''{{su|p=0|b=''12''}} = ''R''{{su|p=-1|b=''1000''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''0201''}} | ''R''{{su|p=-1|b=''1201''}} = ∅ (''a'' | ε)^* ∅ | ''a'' = ''a''

| | = (''a'' | ε)

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

| | ''b''

| | | ''b''

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

|-

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

| | ''R''{{su|p=0|b=''02''}} = ''R''{{su|p=-1|b=''00''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''02''}} | ''R''{{su|p=-1|b=''02''}} = (''a'' | ε) (''a'' | ε)^* ∅ | ∅ = ∅

| | = (''a'' | ε)

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

| | ∅

| | | ∅

| | = ∅

|-

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

| | ''R''{{su|p=0|b=''11''}} = ''R''{{su|p=-1|b=''10''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''0100''}} | ''R''{{su|p=-1|b=''1110''}} = ∅ (''a'' | ε)^* ''b'' | ''b'' | ε = ''b'' | ε

| | = ∅

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

| | (''a'' | ε)

| | | ∅

| | = ∅

|-

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

| | ''R''{{su|p=0|b=''21''}} = ''R''{{su|p=-1|b=''2010''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''01''}} | ''R''{{su|p=-1|b=''2111''}} = ∅ (''a'' | ε)^* ''b'' | ''a'' | ''b'' = ''a'' | ''b''

| | = ∅

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

| | ''b''

| | | ''b'' | ε

| | = ''b'' | ε

|-

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

| | ''R''{{su|p=0|b=''01''}} = ''R''{{su|p=-1|b=''0010''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''0102''}} | ''R''{{su|p=-1|b=''0112''}} = (''a'' | ε) (''a'' | ε)^* ''b'' | ''b'' = ''a''^* ''b''

| | = ∅

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

| | ∅

| | | ''a''

| | = ''a''

|-

| | ''R''{{su|p=0|b=''0020''}}
| | = ''R''{{su|p=-1|b=''0020''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''00''}} | ''R''{{su|p=-1|b=''0020''}}
| | = (''a''∅
| | ε) (''a'' | ε)^*
| | (''a'' | ε)
| ''a''| | ε∅ = ''a''^*

| | = ∅

| | ''R''{{su|p=0|b=''01''}} = ''R''{{su|p=-1|b=''00''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''01''}} | ''R''{{su|p=-1|b=''01''}} = (''a'' | ε) (''a'' | ε)^* ''b'' | ''b'' = ''a''^* ''b''

| | ''R''{{su|p=0|b=''02''}} = ''R''{{su|p=-1|b=''00''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''02''}} | ''R''{{su|p=-1|b=''02''}} = (''a'' | ε) (''a'' | ε)^* ∅ | ∅ = ∅

|-

| | ''R''{{su|p=0|b=''1021''}}
| | = ''R''{{su|p=-1|b=''1020''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''0001''}} | ''R''{{su|p=-1|b=''1021''}}
| | = ∅
| | (''a'' | ε)^* (''a''
| | ε) | ∅''b'' = ∅

| | | ''a'' | ''b''

| | ''R''{{su|p=0|b=''11''}} = ''R''{{su|p=-1|b=''10''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''01''}} | ''R''{{su|p=-1|b=''11''}} = ∅ (''a'' | ε)^* ''b'' | ''b'' | ε = ''b'' | ε

| | = ''a'' | ''b''

| | ''R''{{su|p=0|b=''12''}} = ''R''{{su|p=-1|b=''10''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''02''}} | ''R''{{su|p=-1|b=''12''}} = ∅ (''a'' | ε)^* ∅ | ''a'' = ''a''

|-

| | ''R''{{su|p=0|b=''2022''}}
| | = ''R''{{su|p=-1|b=''20''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''0002''}} | ''R''{{su|p=-1|b=''2022''}}
| | = ∅
| | (''a'' | ε)^* (''a''
| | ε) | ∅ = ∅

| | | ε

| | ''R''{{su|p=0|b=''21''}} = ''R''{{su|p=-1|b=''20''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''01''}} | ''R''{{su|p=-1|b=''21''}} = ∅ (''a'' | ε)^* ''b'' | ''a'' | ''b'' = ''a'' | ''b''

| | = ε

| | ''R''{{su|p=0|b=''22''}} = ''R''{{su|p=-1|b=''20''}} (''R''{{su|p=-1|b=''00''}})^* ''R''{{su|p=-1|b=''02''}} | ''R''{{su|p=-1|b=''22''}} = ∅ (''a'' | ε)^* ∅ | ε = ε

|}