0
$\begingroup$

Given an automaton and an alphabet $\{a, b\} $, and the language accepted by the automaton is $ab^*$.

Such an automata can be found here:

an automaton

My question is: this automaton cannot process the word $ba$ for example. In general, do automata have to be able to process any word?

Improve this question
$\endgroup$
3
  • $\begingroup$ Just add a dead state to which all such cases go $\endgroup$ – vonbrand May 3 '14 at 14:46
  • $\begingroup$ @vonbrand Yes, I did that (completeness) during an exam and that wasn't needed actually. $\endgroup$ – Gabriel Romon May 3 '14 at 14:47
  • $\begingroup$ for informal discussion I'd leave out such niceties $\endgroup$ – vonbrand May 3 '14 at 14:58
3
$\begingroup$

In a deterministic automaton, every state must have exactly one transition for each symbol in the alphabet. In a nondeterministic automaton, this requirement is dropped and there could be multiple transitions or no transition for some symbol. If there is no transition for the next character in the string, the automaton rejects its input. This is what happens with the automaton on the left: it rejects the string $ba$ (and every other string beginning with $b$) because it has nowhere to go when it reads that first $b$.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ @DavidRicherby Is it correct to say that the pictured automaton is nondeterministic because it's missing transitions? I thought we'd just call it an "incomplete" DFA. $\endgroup$ – sjmc May 3 '14 at 9:48
  • $\begingroup$ @sjmc All automata are nondeterministic. A deterministic automaton is the special kind of nondeterministic automaton where there is exactly one transition per symbol per state. $\endgroup$ – David Richerby May 3 '14 at 10:13
  • $\begingroup$ @DavidRicherby Ok, I was thinking of deterministic automata as those with $\textit{at most}$ one transition per alphabet symbol per state, so the pictured automata would be deterministic since the transition relation is in fact a function. (Unless I misunderstand and you were not saying the pictured automata is $\textit{not}$ deterministic). $\endgroup$ – sjmc May 3 '14 at 10:31
  • $\begingroup$ @sjmc The pictured automaton is not deterministic: it does not have exactly one transition per symbol per state. And its transition relation is not a function, for the same reason. $\endgroup$ – David Richerby May 3 '14 at 10:34
  • 2
    $\begingroup$ I disagree with the first sentence; it depends on the definition. It's quite feasible to allow incomplete DFA if the notions of run/acceptance/accepted language are adapted in a suitable way. $\endgroup$ – Raphael♦ May 4 '14 at 10:19
-2
$\begingroup$

An Automaton is supposed to accept only (all) strings that are in some language for which it is defined, and reject any string not in the language.

The automaton on the left, accepts all strings of from $\mathcal{L} = ab^* \equiv {a, ab, abb, abbb, abbbb, ... }$

strings are not commutative, i.e $ab \neq ba$

As you pointed out, it won't accept $ba$ since that's not in $\mathcal{L}$

and in general, automata accept any string in the language.

[by process i assume you mean accept/reject]

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I don't think this answers the question. To me, the OP seems to be asking how the automaton copes with the string $ba$, given that there is no $b$-transition from the start state. $\endgroup$ – David Richerby May 3 '14 at 8:49

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.