Q1 Building NFAs
10 Points
Give a nondeterministic finite automaton (NFA) for the language L of all strings x over the
alphabet \Sigma ={a,b} which have the form x=yz described below.
Substring y is any string which ends on either aaa or abaa.
Substring z is a string of a 's and b 's which has an odd total number of a s.
Examples of strings in L :
aaaa, because (aaa)(a)
aaaaaaa, because (aaaa)(aaa)
aaabaaabaaa, because (aaabaaabaa)(a)
babaabbbab, because (babaa) (bbbab)
Examples of strings not in L :
\Lambda y nor z can be emptybbbbaaay ends on aaa, so there's nothing left for z y must be aaa, but that would mean that z has the wrong number of a^(') 's