I am trying to figure out how to write an NFA which can accept the following language with only 6 necessary states:

{w: number of a's is even OR exactly 2 b's} over the alphabet ∑={a, b} .

Here is an idea for an NFA I had (https://prnt.sc/1ujhoiy) (image provided as link since I don't have the rep to post pictures).

This NFA has the 6 required states and has the needed conditions, but I can't figure out how to OR the 2 conditions together. The aforementioned machine works for simple combinations such as aa, aaaa, bb, but I cant figure out how to connect the two such that inputs baabaa, abbba, abba, baaab, etc... would come out as true.

Thank you in advance.

CodePudding user response：

You can solve this as 2 individual NFA first, 1 for each condition. Connect them together from an initial state q0 with a lambda transition to each of them.

Remember that by default in computer science the OR we use is inclusive, where as in english by default OR is usually an exclusive OR. This might help clear up some edge cases when solving.