Automata and Strings

Question

Can anyone help me with this exercise ? L = {w | w ends with a and does not contain bb} I do not know what I am doing wrong... I have tried creating a automato that contains bb and then changing it so it does not contain it , but then the a problem occurs ,like how am I suppose to make the string always end with a,any help would be appreciated (sorry for my English)

Answer 1

You are on the right track with trying to have a plan for this that involves starting with simple steps. Here is probably where you would have ended up had you give it some thought and written down the steps:

• Make a DFA M1 for all strings containing bb
• Make a DFA M2 for all strings not containing bb by changing M1
• Make a DFA M3 for all strings ending with a
• Make a DFA M4 for all strings ending with a and not containing bb by combining M2 and M3

This plan works fine. We can start with M1. We need an initial state, a state to recognize we have seen one b, and a state to recognize we have seen two b in a row. That last state will be accepting. The DFA would look something like:

M1
      /-\
      | | a
      V /
----->q0--b-->q1--b-->[q2]<----\
       ^      /          |     |
       \--a--/           \-a,b-/

To get M2, we can use a construction which says that given a DFA for L, a DFA for the complement of L can be obtained by switching all accepting states to non-accepting, and vice versa:

M2
       /-\
       | | a
       V /
----->[q0]--b-->[q1]--b-->q2<----\
        ^        /         |     |
        \---a---/          \-a,b-/

For M3, we need to move to an accepting state whenever we see an a, and we need to move away whenever we see a b:

M3
       /---b---\
       |       |
       V       |
----->q3--a-->[q4]<-\
     / ^        |   |
     \b/        \-a-/

For M4, we can use the Cartesian product machine construction by creating a DFA for every pair (qA, qB) of states qA from M2 and qB from M3. We will get 3 x 2 = 6 states:

M4
               /a\
               V |
----->q03--a-->q04
       |       ^ |
       b       | |
       |  /-a--/ |
       V /       /
      q13<---b--/
       |
       b       /-a-\
       |       |   |
       V       V  /
   /->q23--a-->q24
 b |  | ^      |
   \--/ |      |
        \---b--/

It looks like q14 can't actually be reached, so we don't need to include it in the DFA. The states that will be accepting are those that correspond to pairs of states where both states in the pair are accepting. The reason for this is that the connective is "and", i.e., both conditions must simultaneously be true.