Web service is an emerging paradigm for distributed computing. In order to verify web services rigorously, it is important to provide a formal semantics for flow-based web service languages such as BPEL. A suitable formal model should cover most features of BPEL. The existing formal models either abstract from data, cover a simple subset of BPEL, or omit the interactions between BPEL activities. This paper presents Web Service Automata, an extension of Mealy machines, to fulfil the formal model requirements of the web service domain. Secondly, the paper analyses the control handling and data handling of BPEL, so that these can be verified in a clear manner.