Kleene's algorithm: Difference between revisions

Revision as of 19:31, 31 May 2014

Revision as of 19:39, 31 May 2014

Line 138:

Step 1:

{|

{| class=wikitable

|-

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

| | = ''R''{{su|p=10|b=''0100''}} (''R''{{su|p=0|b=''00''}})^* ''R''{{su|p=0|b=''00''}} | ''R''{{su|p=0|b=''00''}}    

| | ''R''{{su|p=1|b= (''02a''}} =| ε)

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

| | (''a'' | ε)

| | | ''a'' | ε    

| | = ''a''^*

|-

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

| | = ''R''{{su|p=10|b=''1100''}} (''R''{{su|p=0|b=''00''}})^* ''R''{{su|p=0|b=''01''}} | ''R''{{su|p=0|b=''01''}}

| | ''R''{{su|p=1|b= (''12a''}} =| ε)

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

| | ''b''

| | | ''b''

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

|-

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

| | = ''R''{{su|p=10|b=''2100''}} (''R''{{su|p=0|b=''00''}})^* ''R''{{su|p=0|b=''02''}} | ''R''{{su|p=0|b=''02''}}

| | ''R''{{su|p=1|b= (''22a''}} =| ε)

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

|}

| | ∅

| | | ∅

Step 2:

| | = ∅

{| class=wikitable

|-

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

| | = ''R''{{su|p=20|b=''0110''}} (''R''{{su|p=0|b=''00''}})^* ''R''{{su|p=0|b=''00''}} | ''R''{{su|p=0|b=''10''}}

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

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

| | (''a'' | ε)

| | | ∅

| | = ∅

|-

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

| | = ''R''{{su|p=20|b=''1110''}} (''R''{{su|p=0|b=''00''}})^* ''R''{{su|p=0|b=''01''}} | ''R''{{su|p=0|b=''11''}}

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

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

| | ''b''

| | | ''b'' | ε

| | = ''b'' | ε

|-

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

| | = ''R''{{su|p=20|b=''2110''}} (''R''{{su|p=0|b=''00''}})^* ''R''{{su|p=0|b=''02''}} | ''R''{{su|p=0|b=''12''}}

| | = ∅

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

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

| | ∅

| | | ''a''

| | = ''a''

|}-

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

| | = ''R''{{su|p=0|b=''20''}} (''R''{{su|p=0|b=''00''}})^* ''R''{{su|p=0|b=''00''}} | ''R''{{su|p=0|b=''20''}}

| | = ∅

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

| | (''a'' | ε)

| | | ∅

| | = ∅

|-

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

| | = ''R''{{su|p=0|b=''20''}} (''R''{{su|p=0|b=''00''}})^* ''R''{{su|p=0|b=''01''}} | ''R''{{su|p=0|b=''21''}}

| | = ∅

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

| | ''b''

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

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

|-

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

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

| | = ∅

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

| | ∅

| | | ε

| | = ε

|}

Step 2:

==References==