What is the language accepted by this NFA? Can you express it in English and with regular expression?

Question

I have been trying to solve this NFA, this below it is the best I could come up with. I have hard time describing in English the language it produces, can someone help me to understand better?

Regular expression

(0+11)*10(0+1(0+11)10)

The automata is not deterministic because there are 3 transactions coming out of P

It does not accept words ending with 0 and an even number of 1. It must have at least one 1 and one zero. Sequences of odd numbers of 1s followed by zero. Or even number of 1s ending with a 0 if there is at least one 10 preceding the series of 1.

Later I have decided that this description is better.

Accept all strings ending with 0 and an odd number of 1, it does not accept strings ending with 1. It will not accept strings ending with 0 and even number of 1.

Accepted words:

1110 1001100110 11010

Not accepted 111001

Answer 1

You can see that you only have 0s going into the accepting state, which means the pattern has to end with a 0.

You also see that you need to have at least one 1, otherwise you will be stuck in the starting state.

Finally, you see that going from the starting state if you get an even number of 1s, you will end up in the start state again.

So, in other words, accepted patterns need to contain an odd number of 1s and end with a 0.

The simplest regular expression I can think of is:

0*(10*10*)*10+

The ending is pretty clear: you need a 1 followed by at least one 0 (so 10+).

The beginning should be quite clear too: you should be able to have as many 0s as you like in the beginning, thus 0*.

Now what remains is (10*10*)* which is 10*10* repeated an arbitrary number of times.

What this represents is any pattern with an even number of 1s which starts with a 1 (the fact that we have 0* just before that ensures that the global expression also covers strings that don't start with a 1).

Note that 10*10* contains exactly two 1s, so no matter how many times you repeat this pattern you will always have an even number of ones.

But how do we know that any string with an even number of 1s would satisfy this pattern?

We can prove this inductively.

A string with no 1s at all will match this expression (if we consider the 0* bit at the beginning) so we have our base case covered.

A string with a positive even number of ones can always be split into a prefix with just two 1s and a suffix with an even number of 1s (this even number may itself be 0).

So what is the expression for a string that contains exactly two 1s?

It's 0*10*10* or 0* followed by 10*10*.

So that's it - our pattern works for an string without any 1s and assuming it works for some even number of 1s we showed that it will work for two additional 1s too. That's basically the entire inductive proof.

A quick note to clarify why we only have 0* once at the beginning:

What happens when you have 0*10*10* followed by another 0*10*10*?

That's right - you get 0*10*10*0*10*10* but since 0*0* is equivalent to 0* we can simply the expression and only have a single 0* at the beginning, omitting it from the repeated expression.