1
$\begingroup$

I have an NFA, and the question I am asked is :

Let 𝑎 < 𝑏 < 𝑐. Now in simple English, express the language of the NFA to explain what type of strings are accepted by it.

In simple English, my answer is

The NFA accepts strings over alphabet {a, b, c} such that the last symbol appears twice.

Which I know is correct, however my problem lies in the question where "a < b < c". How does this affect my NFA and is my answer still correct? My answer seems really short for 6 marks.

$\endgroup$
2
  • 1
    $\begingroup$ Your description is wrong since, for example, aca is not recognized by your automaton. Also, even if we can guess that it is $q_0$, you should indicate clearly what is the initial state. $\endgroup$ – Nathaniel Feb 28 at 20:57
  • 1
    $\begingroup$ What do you mean by $a < b < c$? It's a notation I'm unfamiliar with in this context. $\endgroup$ – Acsor Feb 28 at 21:16
2
$\begingroup$

The automaton accepts all non-empty strings in which the last symbol $\sigma$ appears at least twice, and all symbols appearing between its penultimate appearance and its last appearance are smaller than $\sigma$.

$\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.