Q: Probabilistic automata
Mok-Kong Shen
If I don't err, a probabilistic automata is said to be a generalization
of the non-deterministic finite automata as a consequence of the fact
that the transitions are associated with prescribed probatilitity
values. I don't understand why that's a generalization and not
on the contrary a specialization. In my layman's view, in the case
of the non-deterministic automata the transitions are "unconstrained"
in the sense that frequency of their occurences can be arbitrary and
need not satisfy any given probability values, while in the case of
the probabilistic automata the probability values must be satisfied.
Would someone kindly help me understand the issue?
Thanks.
M. K. Shen
Torben �gidius Mogensen
Generally, a nondeterministic automaton recognizes/generates a string if
there _exists_ a sequence of transitions labelled with the symbols og
the input string that will lead to an accepting state. So the
automation either always recognizes or never recognizes.
A probabilistic automaton assigns probabilities to transitions, so a
given automation will recognize/generate a string with a probabilily
that might be between 0 and 1.
In this sense, you can call it a generalisation, as it gives an answer
that isn't just yes or no (1 or 0) but can be anywhere inbetween.
However, you can't say that probabilistic automata have higher
recognition power than nondeterministic automata.
Torben
Mok-Kong Shen
> Generally, a nondeterministic automaton recognizes/generates a string if
> there _exists_ a sequence of transitions labelled with the symbols og
> the input string that will lead to an accepting state. So the
> automation either always recognizes or never recognizes.
>
> A probabilistic automaton assigns probabilities to transitions, so a
> given automation will recognize/generate a string with a probabilily
> that might be between 0 and 1.
>
> In this sense, you can call it a generalisation, as it gives an answer
> that isn't just yes or no (1 or 0) but can be anywhere inbetween.
> However, you can't say that probabilistic automata have higher
> recognition power than nondeterministic automata.
Being a layman, I am confused. I read on the internet:
The set of languages recognized by probabilistic automata are
called stochastic languages. They include the regular languages
as a subset.
Wouldn't that contradict what you wrote?
Thanks,
M. K. Shen
cplxphil
I think I understand your question, though I'm not sure. Here's my
answer:
A probabilistic machine could be defined by attaching probabilities to
the transitions in the Turing machine, as you suggest. However,
another equivalent definition is to define the machine as a
nondeterministic machine where, instead of checking to see if *there
exists* an accepting computation branch, we check to see if *at least
half* of all computation branches accept. This type of machine is
basically equivalent to a probabilistic machine, because we basically
just select one of the branches at random and see if it accepts. See
for example http://qwiki.stanford.edu/wiki/Complexity_Zoo:R#rp .
So, you're right that a probabilistic machine could be defined by
attaching probabilities to each transition in the machine; but we
could also get the same class of languages by specifying an NDTM and
simply asking, on a given input, "If we select some branch of a
computation at random, is there a greater than (or equal to) 50%
chance that the machine accepts?" This is probably why whatever
source you consulted referred to probabilistic machines as a
generalization of nondeterministic machines.
Does this help?
-Phil
cplxphil
...I think I may have made a slight error in that definition...consult
the link I provided, it's accurate. I think probabilistic machines
are supposed to have more than half of the branches accepting in the
YES instance, and *none* accepting for the NO instances. I'm not
positive though...I have to leave unfortunately or I would correct my
error more carefully. Sorry.
-Phil
Torben �gidius Mogensen
That really depends on the interpretation of how a probabilistic
automaton recognises a string. My interpretation was that it takes
random choices and may sometimes end in an accepting state and at other
times not, even when giving the same input string. You can follow all
transitions simultaniously and for each state in the automaton calculate
the probability of being there at any point, just like you use the
subset construction to emulate an NFA. When you reach the end of the
string, you can add the probabilities of being in each accepting state
to get the probability of the automaton recognising the string. As
such, I defined a recognition function not as mapping strings to
booleans, but to probabilities. This makes it difficult to define the
set of strings that are accepted by the automaton. Generally, any
string that a probabilistic automaton _can_ recognise is also recognised
by a nondeterministic automaton (just remove the probabilities from the
transitions). This led to my statement that it has no extra power.
However, you can also define the set of strings accepted by a
probabilistic automaton as being the set of strings that are accepted
with probability at least p (for some constant 0<p<1). This allows a
probabilistic automaton to distinguish strings that are not
distinguished by a nondeterministic automaton and, hence, increase the
recognition power.
Torben
Mok-Kong Shen
I guess that what I wrote above was not fully clear. Let me quote from
Salomaa's "Theory of Automata":
When scanning the letter x in the internal state s, a
non-deterministic automaton is at liberty to choose one
of the posssible next states. The possible next states are
determined by x and s.
If the states of a finite probabilistic automaton are
s_1,...s_n, then after scanning a letter x in a state s,
PA goes to the state s_i with a probibility p_i(s,x).
So, given a probabilistic automaton with all transitions associated
with probability values, if we delete all the probability values,
the result is a corresponding non-deterministic automaton (NA), isn't
it? The behaviour of NA is unconstrained by the probability values,
but it could certainly, if it likes in a particular case, freely choose
to behave according to the probability values of the corresponding
PA. Right? This clearly shows in my humble view that PA is a
specialization and not a generalization of NA. What's wrong in my
argument?
Thanks,
M. K. Shen
mark
Probabilistic automata are neither specializations nor
generalizations of nondeterministic finite automata. If you think
about it, nondeterministic behavior can't really be simulated by
probabilistic behavior, since nondeterminism is about a free choice
and probabilistic behavior is about following a random path _according
to a fixed distribution_. If you can you should take a look at the
Rabin paper; it's very well written and more clearly motivated than
the wiki article.
Mark
Mok-Kong Shen
> Probabilistic automata are neither specializations nor
> generalizations of nondeterministic finite automata. If you think
> about it, nondeterministic behavior can't really be simulated by
> probabilistic behavior, since nondeterminism is about a free choice
> and probabilistic behavior is about following a random path _according
> to a fixed distribution_. If you can you should take a look at the
> Rabin paper; it's very well written and more clearly motivated than
> the wiki article.
But with free choice, one can "in particular" (freely) choose to act
according to an arbitrary given probatilistic behaviour, can't one?
(Analogy: If one has "free" choice to pick black and white balls, then
one can in particular choose to pick black with probability 1/3 and
white with 2/3, can't one?)
Being a layman, I am confused, because the following quotes apparently
in clear words contradict what you wrote above. Note also that Rabin's
work is mentioned in Salomaa's book, so it could be assumed that there
is no contradiction between Rabin and Salomaa.
http://en.wikipedia.org/wiki/Probabilistic_automaton says:
In mathematics and computer science, the probabilistic automaton (PA)
is a generalization of the non-deterministic finite automaton; it
includes the probability of a given transition into the transition
function, turning it into a transition matrix or stochastic matrix.
A. Salomaa, Theory of Automata, p.73 says:
We shall now introduce the notion of a finite probabilistic
automaton (PA) which is a further generalization of a finite
deterministic and non-deterministic automaton.
M. K. Shen
mark
Well a probabilistic automaton is a generalization of
deterministic finite automata, since we can set all of the transition
probabilities for 1 or 0. But I wouldn't put much weight on the other
relation.
If you are unclear on the meaning of nondeterminism in the context of
automata, you should use the definition of recognition of languages by
NFAs. That is the only definition that matters.
Mark
Barb Knox
<e20c76d1-33d5-42d1...@k9g2000vbl.googlegroups.com>,
mark <mark....@gmail.com> wrote:
Hint: every non-deterministic FA has an equivalent deterministic FA
(i.e. one which recognises exactly the same strings). "Free choice"
does not mean anything mysterious like "free will"; it just means that a
NFA accepts a string if *any* set of choices allows it to accept that
string. IOW, a NFA can be viewed as trying all the possible choice
sequences in parallel (which is how a NFA with a set of states S is
translated to a DFA with a set of states 2^S).
--
---------------------------
| BBB b \ Barbara at LivingHistory stop co stop uk
| B B aa rrr b |
| BBB a a r bbb | Quidquid latine dictum sit,
| B B a a r b b | altum videtur.
| BBB aa a r bbb |
-----------------------------
Mok-Kong Shen
> Well a probabilistic automaton is a generalization of
> deterministic finite automata, since we can set all of the transition
> probabilities for 1 or 0. But I wouldn't put much weight on the other
> relation.
PA generalizes the deterministic finite automaton in that the
transitions have assigned "specific" probabilitity values, while
non-deterministic finite automaton generalizes the deterministic
finite automaton in that the transitions have no specific
assigned probability values, i.e. these are "free" and may have
any arbitrary (chance) value at run time. Is this correct or not?
If yes, then my argumentation regarding generalization between
PA and non-deterministic finite automaton should hold. (Discarding
a constraint is by definition a generalization, at least in math,
if I don't err.)
M. K. Shen
mark
The statement in your first line is correct but your conclusion
does not follow from the first line. You have shown that a certain
characteristic of PFAs is generalized by the corresponding
characteristic in NFAs. However, this reasoning does not extend to the
models in their entirety. You need to look at the definition of
language recognition by NFAs.
Mark
Barb Knox
Mok-Kong Shen <mok-ko...@t-online.de> wrote:
> mark wrote:
>
> > Well a probabilistic automaton is a generalization of
> > deterministic finite automata, since we can set all of the transition
> > probabilities for 1 or 0. But I wouldn't put much weight on the other
> > relation.
>
> PA generalizes the deterministic finite automaton in that the
> transitions have assigned "specific" probabilitity values, while
> non-deterministic finite automaton generalizes the deterministic
> finite automaton in that the transitions have no specific
> assigned probability values, i.e. these are "free" and may have
> any arbitrary (chance) value at run time. Is this correct or not?
Not. See my previous reply to "mark".
> If yes, then my argumentation regarding generalization between
> PA and non-deterministic finite automaton should hold. (Discarding
> a constraint is by definition a generalization, at least in math,
> if I don't err.)
--