NFA or DFA for strings the contain exactly twice substring ab?

Problem Detail: 

Given the language with alphabet: $\{a, b, c\}$ Draw an NFA or DFA for all the strings that have exactly twice substrings $ab$ and at least on $c$. I'm stuck with "exactly twice $ab$". Can somebody give me some ideas. It's also very good if you can suggest me the regular expression of this statement.

Asked By : DucCuong

Answered By : A.Schulz

To answer these kind of questions try to break down your problem into smaller parts.

1. Can you find a NFA that accepts all words that contain the substring $ab$ exactly once?
2. If you have NFAs for the languages $L_1$ and $L_2$. Can you assemble the NFAs to a new NFA that accepts $L_1\circ L_2 =\{uv\mid u\in L_1 \text{ and } v\in L_2\}$?
3. Can you find a NFA that accepts all words that contain a $c$?
4. If you have NFAs for the languages $L_1$ and $L_2$. Can you assemble the NFAs to a new NFA that accepts $L_1\cap L_2 =\{u \mid u\in L_1 \text{ and } u\in L_2\}$?

Steps 2. and 4. are well known closure constructions for regular languages. Its not hard to come up with these constructions by yourself, but there are also part in most of the textbooks.

As pointed out in the comments, the concatenation is in your case more subtle, since the first string might end with $a$ and the second one might start with $b$. This can be fixed by setting $L_1:=\{w \mid \text{$w$ contains $ab$ once in the end}\}$. In particular, you can always split the words of your language exactly after the first occurrence of $ab$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/17942