0
$\begingroup$

I've made the following diagram to accept a, ad, abc, abd but I don't it to accept e, abcd, how can I limit that?

State Diagram

Updated I modified the diagram in another attempt:

State Diagram v2

$\endgroup$
  • 1
    $\begingroup$ Do you know what is N in NFA stands for? Nondeterministic. So you can use more than one $a$ from your initial state. I don’t think you have to use only one final state too. $\endgroup$ – Doralisa Apr 16 '16 at 12:41
  • 1
    $\begingroup$ Please specify the exact language you want to accept. $\endgroup$ – Raphael Apr 16 '16 at 18:27
  • $\begingroup$ Your title mentions not accepting e, but the body of your post doesn't mention that. ​ ​ $\endgroup$ – user12859 Apr 16 '16 at 21:14
  • $\begingroup$ @RickyDemer Fixed it. $\endgroup$ – Django Apr 16 '16 at 21:24
2
$\begingroup$

Your automaton has loops so it accepts an infinite language.

For finite languages $\{w_1, \dots, w_n\}$, it's easy to write them as regular expression

$\qquad w_1 \mid \ldots \mid w_k$

and apply Thompson's construction. If the resulting automaton is too ugly for your taste, determinize and minimize according to the canonical textbooks.

Warning: Determinizing automata for finite languages can blow up automaton size exponentially.

Note how this approach scales neatly to more concise representations of finite languages and even infinite languages -- all you need is a regular expression. Or any other formalism equivalent to finite automata, as the proofs of equivalence are usually constructive.

$\endgroup$
  • $\begingroup$ I need to do it without regular expressions and I'm not familiar with Thompson's Construction. I've updated the question with another diagram which I think could be the correct answer now. $\endgroup$ – Django Apr 16 '16 at 11:33
  • 1
    $\begingroup$ 1) Thompson's construction is elementary; you should understand it from the Wikipedia article. 2) That one still has a loop, and it still accepts $abcd$. You can easily check that yourself. (Maybe we need to adjust your expectations: this is not a homework-solving or -grading site. I gave you a structured approach to solve your problem -- the work is yours.) $\endgroup$ – Raphael Apr 16 '16 at 11:35
  • $\begingroup$ This is not a homework assignment, it is an exercise I found and I'm unable to solve it correctly, I already mentioned that I don't want to use regular expressions because I haven't studied regular expressions yet. Thompson's Construction technique is not what I'm looking for because I'm not trying to transform regular expressions into NFAs. I'm just trying to design an NFA that accepts the specified strings. I'm trying to understand what is it that I'm doing wrong or what is it that I am missing so I can do it right if you wanna help me with that I'll be grateful. $\endgroup$ – Django Apr 16 '16 at 11:42
  • $\begingroup$ As I said: don't create loops. Don't try to create a small automaton. Don't try to be clever. $\endgroup$ – Raphael Apr 16 '16 at 12:36
  • 3
    $\begingroup$ (By the way, "I don't want to learn about X because I have not yet learned about X" is a weird way to argue for a learner.) $\endgroup$ – Raphael Apr 16 '16 at 12:37
1
$\begingroup$

Just make an automaton that looks like a tree, for each state splitting into the possible letters.

In data structure terminology such a tree with leters on edges is called a trie, as in re-trie-val.

$\endgroup$
0
$\begingroup$

This is the correct answer for the specified specification:

Solution

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