-3

I am really new to this and to sure how to start. I am trying to do this question for practice

Let segma = {a,b}. Consider the set of all strings in segma* that have an odd number of occurrences of the substring "ab" but do not have "bb" as a substring. Give a DFA with six states accepting the set.

I did change my solution.

Attempt

3
  • 1
    Why don't you give it a try, and then see if you end up with six states? Nov 13, 2014 at 3:36
  • @JasonBaker. I did try but I am not sure how to start, that is why I put this question.
    – Alex
    Nov 13, 2014 at 3:40
  • I hav made this solution and not sure if I am in the right track or not s4.postimg.org/3wdpz9bv1/… Please any suggestions
    – Alex
    Nov 15, 2014 at 3:55

1 Answer 1

0

Here is an idea of how to approach this question. Think about the conditions you need to meet.

First, you need to have an odd number of "ab", which means your DFA should have a "counter" loop that every time you encounter odd number of "ab", your DFA will be in a state, such that this state has an edge that allows your DFA to move toward the accepting state. Conversely every time you encounter even number of "ab", your DFA should be in a state, such that this state cannot move forward, unless you encounter another "ab".

Second, the string cannot have "bb". This means that if you ever encounter a single "b", a subsequent "b" will drive your DFA to a sink, which means your DFA rejects the string.

It might be easier to associate each character condition to the edges, so that if a certain condition is met, your DFA can move to a certain state.

7
  • Thanks. This is really helpful. I will try do as you suggested and I will post my solution to see if I need to fix it
    – Alex
    Nov 13, 2014 at 4:09
  • I did solution and I am not sure if that is correct. Please check the link s4.postimg.org/3wdpz9bv1/…
    – Alex
    Nov 15, 2014 at 3:41
  • @Alex I don't think your solution is correct. Try passing in "bab" to your DFA and see which state can you end up with. Currently it doesn't even pass the start state. Meanwhile you can use several other strings to test your DFA. e.g. "babab" "bababab" "abbb" "abaabab" "aaaaaaaaaabaababb"...
    – StoneBird
    Nov 16, 2014 at 3:26
  • I did modify my solution. I hope you can look at it
    – Alex
    Nov 18, 2014 at 7:23
  • @Alex makes much more sense to me. I think this one works well. Did you check other strings?
    – StoneBird
    Nov 18, 2014 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.