0
$\begingroup$

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

Can i create a NFA Like this

enter image description here

$\endgroup$
  • $\begingroup$ You can create an NFA like that, sure, but that one doesn't accept $L$, it accepts all nonempty strings of $a$ and $b$. $\endgroup$ – BrianO Nov 30 '15 at 12:41
  • $\begingroup$ @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. $\endgroup$ – techno Nov 30 '15 at 12:45
  • 1
    $\begingroup$ 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. $\endgroup$ – BrianO Nov 30 '15 at 13:02
  • $\begingroup$ @BrianO Please take a look here and let me know if he is wrong youtu.be/ZjjAbFxjxLQ?t=3m5s $\endgroup$ – techno Nov 30 '15 at 13:05
  • $\begingroup$ 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. $\endgroup$ – BrianO Nov 30 '15 at 13:10
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Sorry i forgot drawing the second circle.Please see the update. $\endgroup$ – techno Nov 30 '15 at 12:38
  • $\begingroup$ 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. $\endgroup$ – techno Nov 30 '15 at 12:47
  • $\begingroup$ @techno Thanks for the update - but the second part of my answer is still appropriate. I'll modify the first part to update on the current image. $\endgroup$ – kviiri Nov 30 '15 at 12:49
  • $\begingroup$ @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. $\endgroup$ – kviiri Nov 30 '15 at 12:52
  • $\begingroup$ Can you please take a look at this and let me know if he is wrong youtu.be/ZjjAbFxjxLQ?t=3m5s $\endgroup$ – techno Nov 30 '15 at 12:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.