2

I know how to apply Kleene star on language but I'm not sure how would I apply it to DFA or NFA. I'm pretty sure it would need to be epsilon NFA with initial state that is final and final states might need epsilon transition to that initial state?

Is there any algorithm for this? How would this DFA that accepts words that starts with 0 and end with 1 look after Kleene star was applied to it? enter image description here

qu4lizz
  • 317
  • 2
  • 12

1 Answers1

2

In at least one proof I've seen of the equivalence of regular expressions and finite automata, a construction is given to show how to turn a NFA with a language corresponding to that of a regular expression s into a NFA with a language corresponding to that of the expression s*. I think the construction goes like this:

  1. new initial state q0' that is also accepting
  2. lambda/epsilon/empty transition from q0' to the former initial state q0
  3. lambda/epsilon/empty transitions from every accepting state (except q0') back to q0'

This allows:

  1. the empty string to be accepted, even if it wasn't before
  2. any concatenation of strings from the language of the original NFA to be accepted
Patrick87
  • 27,682
  • 3
  • 38
  • 73
  • 1
    The construction operates on NFAs with epsilon transitions, which includes DFAs. To get a DFA out, we have to convert back to a DFA using the subset construction and optionally minimize it. On the particular DFA in the question, the overall effect will be to make q0 accepting and either delete q3 or add the missing self-transition on 0,1 depending on whether a partial transition function is allowed. – David Eisenstat May 06 '22 at 12:26
  • @DavidEisenstat I updated based on your comment, you're of course right the construction uses NFAs not DFAs. – Patrick87 May 06 '22 at 12:41
  • I don't think those are all steps. If I add those epsilon transitions and leave self-transitions in final state (q2), that NFA would accept word 010, even though it doesn't end with 1. – qu4lizz May 06 '22 at 18:11
  • Well your NFA already accepts 010 the way it's written. To accept only strings that end with 1 you'd need the transition from q2 on 0 to return to q1. @qu4lizz – Patrick87 May 06 '22 at 18:23
  • Yep, I didn't construct it well. Makes sense now, will fix it in the post. – qu4lizz May 06 '22 at 18:38
  • So this would be it? https://imgur.com/a/BmG1KfR – qu4lizz May 06 '22 at 18:43
  • @qu4lizz yes the NFA you have now appears to accept the right language – Patrick87 May 06 '22 at 20:12