# NFA Containing 'a'

I have L={Contains 'a'} and Alphabet(E)={a,b}

Can i create a NFA Like this • You can create an NFA like that, sure, but that one doesn't accept $L$, it accepts all nonempty strings of $a$ and $b$. – BrianO Nov 30 '15 at 12:41
• @BrianO okay got it.Say the string is bb, there will be transition from Q1 to Q2 (but no 'a') still ,it gets accepted.So i need an Edge labelled a from Q1 to Q2.Q1 and Q2 having edges labelled a,b to them. – techno Nov 30 '15 at 12:45
• That's right. However, there's no reason to have two edges labelled $a$ from Q1, one edge looping to Q1 and the other advancing to Q2. Just use one edge Q1 -> Q2 on $a$. The machine will actually be a DFA. – BrianO Nov 30 '15 at 13:02
• @BrianO Please take a look here and let me know if he is wrong youtu.be/ZjjAbFxjxLQ?t=3m5s – techno Nov 30 '15 at 13:05
• I didn't say it's wrong, it's just unnecessary, and can be further simplified, as described. In that machine (in the vid), it's nondeterministic which $a$ of a string transitions to the accepting state. If instead the $Q_1$ edges are $Q_1\stackrel{b}\to Q_1$ and $Q_1\stackrel{a}\to Q_2$, then the transition to $Q2$ always happens on the first $a$ in an accepted string. This machine is deterministic and even has one fewer transition. – BrianO Nov 30 '15 at 13:10

Any non-empty string winds up in Q2 and stays there, so you match more than you should. For example, $bbb$ is accepted even though it's not in $L$.
The initial state should keep reading input until $a$ is read, and the other one should be the accepting state and just consume the rest of the input by looping any input to itself.
• @techno Yeah, that's correct. But you need to remember to loop Q1 --> Q1 if you read a $b$, because otherwise you'd reject a string for containing a $b$ which shouldn't happen. – kviiri Nov 30 '15 at 12:52