Finding DFA of r* when r and DFA of r were deifined

Question

I would like the example that method to find DFA of r* when the r and DFA of r were defined . And how to thinking ? I read a textbook but I don't understand clearly. Thank you.

Answer 1

r* is the language that contains all strings that are concatenations of 0,1,2,3,4,... strings from r. So the obvious FA for r* is one that can run the DFA for r 0,1,2,3,4,... times and accept after any one of these runs. A lambda/empty transition from any accepting state to the start state will achieve 1 or more runs. The resulting automaton is not deterministic anymore. You can use a standard method to determinize it. This construction does not add the empty string to the automaton's language. If it already is there in r, this is not necessary. Otherwise you need to add a way of accepting the empty string in the automaton for r*, for example with a new start state.

With a little experience in eliminating empty transition you can also construct a DFA more directly for simple cases.

Answer 2

Regular Expression: r* is a regular expression corresponding to the language L[R*] where L(R*)=(L(R*))

Ex:-

(0+10*)={0,1,10,100,1000,10000,......}

(0 * 10*)={0,01,001,010,01000,0010,.....}

(aa + ab + ba + bb)*={aa, ab, ba, bb, aaab, aaba, …………..}

if X+Y is a regular expression corresponding to the language L(X+Y)=L(X)+L(Y)

if X.Y is a regular expression corresponding to the language L(X.Y)=L(X).L(Y)

R* to DFA:-

To construt to regular expression to DFA first construct the NFA and then convert NFA to DFA

r=(a|b)*abb#

fist construct the augmented regular expression for the given expression like

r'=(a|b)*abb#

construct the syntax tree for # like below figure

Next we need to evolute the four function nullable,firstpos,lastpos and followpos.

We refer to an interior node as a cat-node, or-node, or star-node if it is labeled by a concatenation, | or * operator, respectively.

1. If n is a cat-node with left child c1 and right child c2 and i is a position in lastpos(c1), then all positions in firstpos(c2) are in followpos(i).

2. If n is a star-node and i is a position in lastpos(n), then all positions in firstpos(n) are in followpos(i).

3. Now that we have seen the rules for computing firstpos and lastpos, we now proceed to calculate the values of the same for the syntax tree of the given regular expression (a|b)*abb#.

4. Now we construct Dstates, the set of states of DFA D and Dtran, the transition table for D. The start state of DFA D is firstpos(root) and the accepting states are all those containing the position associated with the endmarker symbol #.

According to our example, the firstpos of the root is {1, 2, 3}. Let this state be A and consider the input symbol a. Positions 1 and 3 are for a, so let B = followpos(1) ∪ followpos(3) = {1, 2, 3, 4}. Since this set has not yet been seen, we set Dtran[A, a] := B.

When we consider input b, we find that out of the positions in A, only 2 is associated with b, thus we consider the set followpos(2) = {1, 2, 3}. Since this set has already been seen before, we do not add it to Dstates but we add the transition Dtran[A, b]:= A.

Continuing like this with the rest of the states, we arrive at the below transition table.

Now we construct the DFA for the following transctions: