1
$\begingroup$

I designed this transition graph, seen below. The alphabet contains {a, b, c}, and the goal of this machine is to accept any strings (no limitations on length of string) that ends with a letter that is already in that string.

Example: abba, aaa, bb, ababababacc, cabc are accepted. Example: abc, bccba, a, b, c, cccab, are a rejected.

Is there a shorter/simpler way to design this finite automata than this transition graph?

Finite Automata

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Any decent textbook should tellyou how to minimize a DFA. Have you tried that? $\endgroup$ – D.W. Sep 26 '15 at 5:14
  • 1
    $\begingroup$ While this is an NFA, where minimization is harder, you can still identify and merge states which are bisimilar. In particular, your states $q10,\dots,q15$ are all essentially equivalent; after merging these, you can do the same to the pairs $(q4,q6),(q5,q8)$ and $(q7,q9)$. $\endgroup$ – Klaus Draeger Sep 26 '15 at 9:57
3
$\begingroup$

Each string that is input to an automaton takes you to some state. So you can see each state an encoding some kind of information about the inputs the machine has seen if it's in that state. For example, an automaton might have a state that corresponds to "all words with an even number of $b$s."

Why am I telling you this? Because, when you're designing an automaton, it's often helpful to think about what information you need to store about the input to accept the language you want. In this case, you want to accept all words whose last letter has already appeared in the string. So, the information you need to decide the language is "What letters have I seen so far?" If you encode that information in some states of the automaton, it should be easy to add the right transitions to accept the language you want.

$\endgroup$
1
$\begingroup$

When faced with tasks as building an automata it may be sometimes useful to think about decomposing the automata into smaller parts, and then using union or concatenation or repetition to build the whole thing.

For your task, think about a regular expression $(a+b)^*c(a+b+c)^*c$ as corresponding to only one of the possible cases, viz. the case which only finds the words having $c$ repeated at least twice. You may use the same idea to construct automata for $a$ and $b$, and then take the union of the three. The resulting graph will be roughly the half of what you have now.

$\endgroup$
  • $\begingroup$ That regular expression isn't any of the cases. It matches $cca$, which isn't in the language. $\endgroup$ – David Richerby Sep 26 '15 at 11:14
  • $\begingroup$ @DavidRicherby Oh, I misread it, I thought it has to contain the repetition of the same later. Having to end in the same letter will be even easier (I'll fix the expression to match that). $\endgroup$ – wvxvw Sep 26 '15 at 16:44

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.