Question

1. Construct a DFA that accepts a string{a,b} with bb being followed by ab.

Answer 1

Answer:

How can I construct finite automata in which 'a' is immediately preceded and followed by 'b'?

To approach such questions, first we should try to generate a few strings in which ‘a’ is immediately preceded and followed by ‘b’. Generate these strings using string length, starting from small to large and continue until we see a clear pattern.

String of zero length 0-

ε

String of length 1-

a, b

Strings of length 2-

aa, ab, ba, bb

Strings of length 3-

aaa, aab, aba, abb, baa, bab, bba, bbb

String of length 4-

aaaa, aaab, aaba, aabb, abaa, abab, abba, abbb, baaa, baab, baba, babb,bbaa, bbab, bbba, bbbb

If we observe above strings closely, we can see that in only strings bab, babb, bbab, ‘a’ is immediately followed and preceded by ‘b’, so we will include these strings in the set and generate more strings of length 5,6 and 7 of such kinds.

Refer the following set of strings-

{bab, babb, bbab , bbbab, babbb, babab, bbbbab, babbbb, babbab,bababab, --)

If we analyze the above set we can clearly see a pattern in the string. Above set has three kinds of strings-

Strings in which “bab” is preceded by any number of b’s and followed by any no of ‘b’s.

Strings in which “bab” is preceded by any number of “ba” and followed by any no of “ab”

Strings in which “bab” gets repeated any no of times.

Step-1 Construct a DFA that accepts string - “bab”

Step-2 Add self loop using input symbol b on state B and D to accept strings in which “bab” is immediately preceded and followed by any number of b’s-

Step-3 Add a transition from state D to State C using input symbol a to accept strings in which “bab” gets repeated multiple times.

Step-4 Add a dummy state E