Final answer:
NFA and DFA constructions require careful state and transition planning for different language restrictions. NFAs may have states with multiple possible transitions for a given input symbol, while DFAs have exactly one transition per input symbol for each state.
Step-by-step explanation:
Designing NFAs and DFAs
To design an NFA for a set of all strings over {a,b,c} that do not contain aa, bb, or cc, you would ensure state transitions do not allow for consecutive identical letters. For instance, from the starting state, if you read an 'a,' you transition to a state that can only read 'b' and 'c', and similar for 'b' and 'c'.
For the language L={an : n ≥ 0} ∪ {bmak : m, k ≥ 0}, an NFA with no more than 3 states could have a start state accepting 'a' any number of times and a transition on 'b' to another state, which loops on 'b' and has a transition on 'a' to a third state that loops on 'a'.
L={anbm: n≥3, m is even} can be represented with an NFA that starts in a state which transitions to a second state upon reading 'a'. After reading three 'a's, it would transition to a final state, which loops on 'b' and transitions to itself on every second 'b' read to ensure that 'm' is even.
For the DFAs:
Words with two or three letters 'a' and also the empty word: A DFA could start in an accept state and transition to other accept states upon reading 'a' but would have a reject state if a fourth 'a' is read.
- Words with an even number of 'a's and an odd number of 'b's: This could be a four-state DFA that changes states based on the parity of 'a's and 'b's read.
- Words of even length without two consecutive 'a's: This DFA may be represented by two states, one representing even and the other odd lengths, with appropriate transitions for 'a' and 'b'.
- Words every occurrence of 'bb' is preceded by 'aba': A DFA for this language would require more states to track the specific pattern of 'aba' followed by 'bb'.