Question

Construct a nondeterministic finite automaton (NFA) that will accept all strings with the substring 111 but not 1111.

Note that consecutive 1111's aren't acceptable at all .

Ex: 1111011 is not acceptable ,111011 is acceptable

Answer 1

The strings must contain 111 as the substring.

After 111, we can have 0's immediately

But after 111, we can't have 1 immediately

So, we need to construct an NFA for those strings that have 111 as a substring.

Strings of length 3

111

Strings of length 4

0111

1110

Strings of length 5

00111

10111

11100

11101

01110

The NFA is given below

Please don't forget to give a positive rating to the answer. Your rating motivates experts to help other students also. Thank you :)