Skip to content

Lecture No. 11

Dated: 26-10-2024

Let's prove the 2nd statement of kleene's theorem.1
To prove that a transition graph2 can represent a regular expression,3 we will develop an algorithm which converts the transition graph2 into generalized transition graph4
The transition graph4 we want to convert is the following.
CS402_i_11_1.png

Step 1

If a transition graph2 has more than one initial states then make one initial state, connecting the old initial states.
CS402_i_11_2.png

Step 2

Repeat the step 1 but for final states.
CS402_i_11_3.png

Step 3

If there are 2 states connected with more than one transition edges, including the loops, convert these edges into one edge.

CS402_i_11_4.png
this can be converted into
CS402_i_11_5.png
This works with any number of transition edges.

Step 4

If 3 states are connected in a sequence, then we can skip the middle state.
Connecting the first state with the last one with the transition edge labeled as the concatenation of the regular expressions3 of all the edges.

CS402_i_11_6.png
can be converted into
CS402_i_11_7.png

Example

CS402_i_11_8.png
Can be converted into
CS402_i_11_9.png

Example

CS402_i_11_10.png
This can be converted into
CS402_i_11_11.png
Which can further be converted to
CS402_i_11_12.png

References

  1. Read more about kleene's theorem. ↩

  2. Read more about transition graphs. ↩↩↩

  3. Read more about regular expressions. ↩↩

  4. Read more about transition graphs. ↩↩