2
$\begingroup$

Consider the non-deterministic finite automaton A: (in below figure)

1> convert this NFA to DFA

2> Find if there are equivalent states of your DFA

3> Minimize the DFA of <2> if possible

enter image description here

This is what i have got so far

enter image description here

enter image description here

4> further question: Prove that the DFA in <3> recogniese the intended language L.

I got stuck on this question, since the language says that "every occurrence of a is preceded by and followed by an occurrence of b" this means:

L = {x bab)^n y | x,y belongs to {b,empty}^n where n is natural number}

In this case: the language can be: bbb.....bbbb bab ... bab bbb....bbbb

But for my <3> DFA, the occurrence of a can appear without preceded by an occurrence of b.

I hope if there is anyone can point out my mistake.

many thanks

$\endgroup$
1
$\begingroup$

Here is the transition table for your NFA:

q    s    q'
S0   b    { S1 }
S1   b    { S1, S2 }
S1   a    { S2 }
S2   b    { S1 }

There are a few problems that prevent this from being a DFA:

  1. Two valid transitions from state $S_1$ on $b$;
  2. No valid transition from $S_0$ on $a$;
  3. No valid transition from $S_2$ on $a$.

Problems (1) and (3) can be solved by introducing a new, "dead", state, $S_3$; the transition table becomes:

q    s    q'
S0   b    { S1 }
S0   a    { S3 }
S1   b    { S1, S2 }
S1   a    { S2 }
S2   b    { S1 }
S2   a    { S3 }
S3   b    { S3 }
S3   a    { S3 }

To solve problem (2), we can simply note that the transition $S_1 \rightarrow bS_2$ doesn't buy us anything in terms of strings accepted; the only way to get to an accepting state after doing that is to take the transition $S_2 \rightarrow bS_1$, and we could simply have applied the transition $S_1 \rightarrow bS_1$ twice to do the same thing. We can simply remove this transition and the resulting NFA accepts the same language. Here's the transition table:

q    s    q'
S0   b    { S1 }
S0   a    { S3 }
S1   b    { S1 }
S1   a    { S2 }
S2   b    { S1 }
S2   a    { S3 }
S3   b    { S3 }
S3   a    { S3 }

We have no $\lambda$-transitions and each transition maps to a singleton set of states; this defines the following DFA:

q    s    q'
S0   b    S1
S0   a    S3
S1   b    S1
S1   a    S2
S2   b    S1
S2   a    S3
S3   b    S3
S3   a    S3

Now, we may argue using the Myhill-Nerode theorem to see whether we have redundant states. Consider the ways to get to a string in the language from state $S_0$. We can see any string in the language (by definition) and end up in an accepting state. This state constitutes an equivalence class we have not yet observed.

Consider $S_1$. Our first observation is that any string in the language, if encountered starting at this state, will also lead to an accepting state, hence another string in the language. However, we can also see the string $ab$, among others, so this constitutes a new equivalence class, and the state is required.

Consider $S_2$. Any string in the language, except $\lambda$, leads to an accepting state of the DFA. This is a new equivalence class and the state is not redundant.

Consider $S_3$. No strings lead from here to an accepting state, so this is yet another equivalence class under the indistinguishability relation, and the state must be kept.

Therefore, the DFA whose transition table is given above is minimal for the language it accepts. Furthermore, it accepts the language of the NFA originally proposed.

To prove the DFA accepts the target language, there are a variety of approaches. The easiest one is actually by stating three facts about the syntax of your DFA, which prevents the excluded condition from occurring in any accepted strings:

  1. The transition from $S_0$ on $a$ leads to a dead state (no string begins with $a$);
  2. There is no transition to an accepting state on $a$ (no string ends with $a$);
  3. Applying $q \rightarrow aq'$ and $q' \rightarrow aq''$ consecutively always leads to the dead state, where these transitions are any of those in the DFA (no string contains $aa$).

I suppose this is a proof by cases, if knowing what to call the proof is important :D

$\endgroup$
1
  • $\begingroup$ thanks a lot. I checked your equivalence states tables, which will provides the same minimal DFA output as i written. (if you let your s1 be my s112; and s3 be my empty state). $\endgroup$ – Ashfalano Oct 16 '13 at 15:26

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.