zbMATH — the first resource for mathematics

On prefixes of formal languages and their relation to the average-case complexity of the membership problem. (English) Zbl 0867.68070
Summary: Given a formal language \({\mathcal L}\) over an alphabet furnished with a probability distribution, we present a simple general approach to the computation of the average length of the shortest prefix which has to be read in order to decide whether or not a given word of length \(n\) belongs to \({\mathcal L}\). This approach covers a complete average-case analysis of that parameter, including higher moments about the origin and the cumulative distribution function. We demonstrate our results by discussing various concrete languages, such as regular sets, Dyck sets, permutations, well-known languages encoding trees, etc.

68Q45 Formal languages and automata