0
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ This answer seems to suggest that if I represent the language $K$ of strings with $ab$ exactly once, and I know how to do concatenation, then I also know the representation of the language that has $ab$ exactly two times. Note that latter language is not equal to $K\circ K$. $\endgroup$ – Hendrik Jan Nov 12 '13 at 21:06
  • $\begingroup$ @HendrikJan, I agree, in this case, $ababab\in L_1\circ L_2$ from bullet 2, since $aba\in L_1$ and $bab\in L_2$. $\endgroup$ – avakar Nov 13 '13 at 12:07
2
$\begingroup$

Think of programming. What variables would you introduce if you had to write a program that tests a string letter-by-letter for two occurrences of $ab$ and at least once $c$?

  • ab-count: with values 0,1,2, too-much
  • seen-c: a boolean
  • last-letter-was-a: a boolean. We want to count $ab$ occurrences, so a $b$ after $a$ is special, and we have to remember whether the previous letter read was $a$ to do this.

What do we do when we read $a$. We set last-letter-was-a to true.

What do we do when we read $b$. If last-letter-was-a is false, then we add one to ab-count (and all numbers more than 2 are stored as too-much). We set last-letter-was-a to false.

What do we do when we read $c$. We set last-letter-was-a to false. We set seen-c to true.

This is your finite state automaton. Each state represents a triple (ab-count, seen-c, last-letter-was-a ). Think about initial and final states.

$\endgroup$
1
$\begingroup$

$DFA\ \ M = (Q, \delta, q_0,q_a)$

where,

$Q = \{q_0,q_1,q_2,q_3,q_4,F=\{q_a,q_4\}\ \ \}$ and

$ \delta : $

$(q_0,a) \rightarrow q_1 \\ (q_0,b) \rightarrow q_0 \\ (q_0,c) \rightarrow q_0 \\ (q_1,a) \rightarrow q_1 \\ (q_1,b) \rightarrow q_2 \\ (q_1,c) \rightarrow q_0 \\ (q_2,a) \rightarrow q_3 \\ (q_2,b) \rightarrow q_2 \\ (q_2,c) \rightarrow q_2 \\ (q_3,a) \rightarrow q_3 \\ (q_3,b) \rightarrow q_a \\ (q_3,c) \rightarrow q_2 \\ (q_a,a) \rightarrow q_4 \\ (q_a,b) \rightarrow q_a \\ (q_a,c) \rightarrow q_a \\ (q_4,a) \rightarrow q_4 \\ (q_4,b) \rightarrow q_5 \\ (q_4,c) \rightarrow q_a\\ (q_5,a) \rightarrow q_5 \\ (q_5,b) \rightarrow q_5 \\ (q_5,c) \rightarrow q_5 \\$

Regular expression of string that does not have "ab" substring = $(a^*c^+b^*c^*)^* = S $ say then $SabSabS$ is the required RE

$\endgroup$
  • $\begingroup$ But we also want 'at least one c' $\endgroup$ – phs Nov 12 '13 at 14:06
  • $\begingroup$ What is the idea here? How can you use this answer to learn how to do other, similar exercises yourself? $\endgroup$ – Raphael Nov 14 '13 at 13:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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