0
$\begingroup$

I understand that in a non-deterministic automaton, an input can lead to one, more than one, or no transition for a given state.

Given this information, I would assume that if the input lead to a loop, this loop would be infinite until a determined input happened (being one || more || ε).

However I would like to know if there's a way to represent a "finite" loop with an NFA. For example, an ATM where a person only has a determined amount of chances to get the password right. If not, the operation is cancelled.

The input is always the same (0-9 digits), so how can the outcome be different after 3 tries?

Thank you for any hints on this!

$\endgroup$
2
  • $\begingroup$ This will not be a loop, it will just be 3 different "states" (where "states" here represent all the states at the current try of the password). Also, this is exactly how you would do this in a deterministic automaton. $\endgroup$
    – nir shahar
    Feb 19, 2021 at 14:24
  • $\begingroup$ Ok! I actually made this attempt: ibb.co/Nx4mvnc Is this ok? Thank you! $\endgroup$
    – OcR19
    Feb 19, 2021 at 14:40

2 Answers 2

2
$\begingroup$

Let's assume the user needs to enter a password and then press OK. Let's assume the password is 42:

enter image description here

But let's say the user makes a mistake, how can we allow three tries? By adding failure states, waiting for OK, and if we're in a failure state when OK gets pressed we get another try. Let $*$ notate 'anything else' - any character that wasn't handled by another arrow.

enter image description here

$\endgroup$
0
$\begingroup$

Some of this depends on what you mean by "tries." But here is a reasonable first whack.

Suppose that the password is ab and you want to give a person two tries. Take q0 to be the initial state, take q2 to be the only accepting state, take q3 to mean "first try failed, initalize second try" (and it might light a light, warning the inputter that their first try failed). Also take q5 to be the (non-accepting) state meaning two-try failure.

Coming from q0 are two arrows, one to q1 labeled a and one to q3 labelled b. From q1 are two arrows, one to q2 labeled b and one to q3 labeled a. From q2 is a loop, labeled any.

You get the idea. From q3 are two arrows, one to q4 labeled a and one to q5 labeled b. From q4 come two arrows, one to q2 labeled b and one to q5 labeled a. From q5 is a loop, labeled any.

This is of course hopelessly naive from a security standpoint. But it gets across the basic idea.

$\endgroup$

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.