Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: Stochastic Finite State Automaton
Description The finite state automaton (FSA) is an important model of behavioral investigations in computer science, linguistics as well as many other different areas of study. In theoretical computer science literature, an FSA is typically modeled as a string pattern recognizer described with a quintuple <Σ, - Σ is the input alphabet (a finite nonempty set of symbols).
*S*is a finite nonempty set of states.*s*_{0}is an element in*S*designated as the initial state.*δ*is a function*δ*:*S*× Σ →*S*known as the transition function.*F*is a (possibly empty) subset of*S*whose elements are designated as the final states.
An FSA with the above description operates as follows: - At the beginning, the automaton starts in the initial state
*s*_{0}. - The automaton continuously reads symbols from its input, one symbol at a time, and transits between states according to the transition function
*δ*. To be specific, let*s*be the current state and*w*the symbol just read, the automaton transits to the state given by*δ*(*s*,*w*). - When the automaton reaches the end of the input, if the current state belongs to
*F*, the string consisting sequentially of the symbols read by the automaton is declared accepted, otherwise it is declared rejected.
We will not delve into further details concerning the FSA but focus on a slightly simplified variant – the stochastic finite state automaton (SFSA). An SFSA is described with a duple < >, where:bis an*A**n*-by-*n*nonnegative square matrix.is an*b**n*-dimensional nonnegative column vector.
The automaton assumes the first - At the beginning, the automaton selects randomly a positive integer not exceeding
*n*,*i*, as the initial state with probability*b*_{i}, the*i*-th component of. (It is required that the components of*b*sum to exactly 1.)*b* - At any stage before the automation halts, let
*j*be the current state, the automaton selects randomly a positive integer not exceeding*n*,*i*, with probability*a*_{ij}, the element oflocated in the*A**i*-th row and the*j*-th column, or 0 with probability . If the automaton selects 0, it halts immediately, otherwise it transits to state*i*. (It is required that the sum of elements of every column ofbe not less than or equal to 1.)*A*
Deriving from the above description, we can draw several implications concerning the SFSA. For instance, observably, the automaton may make an infinite number of transits and never halt, but intuitively, this is very unlikely to occur. Before scrutinizing the behavioral features of the SFSA, it is advisable to first investigate its statistical characteristics, namely, we want to know for each state Input The input consists of a single test case. The first input line contains the number n nonnegative numbers which are the components of an n-dimensional column vector in increasing order of their indices. The sum of elements in every column of b is Astrictly less than 1, and the components of sum to exactly 1. The duple <b, A> constitutes the description of an SFSA.bOutput For each state in increasing order of their numerical values, output in order and as accurate as possibly the probability that the automaton decides to halt in that state and, given that automaton halts in that state, the expectation as well as the standard deviation of the number of transitions that have been made. A special checker program that admits an relative error of 10 Sample Input 3 0.25 0 0 0.25 0 0 0.25 0 0 1 0 0 Sample Output 0.33333333 0.33333333 0.66666667 0.33333333 1.33333333 0.66666667 0.33333333 1.33333333 0.66666667 Hint For a random variable Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator