Computer Science – Formal Languages and Automata Theory
Scientific paper
2010-07-07
Computer Science
Formal Languages and Automata Theory
14 pages, 6 figures
Scientific paper
Let $\mathcal{P}(\Sigma^*)$ be the semiring of languages, and consider its subset $\mathcal{P}(\Sigma)$. In this paper we define the language recognized by a weighted automaton over $\mathcal{P}(\Sigma)$ and a one-letter alphabet. Similarly, we introduce the notion of language recognition by linear recurrence equations with coefficients in $\mathcal{P}(\Sigma)$. As we will see, these two definitions coincide. We prove that the languages recognized by linear recurrence equations with coefficients in $\mathcal{P}(\Sigma)$ are precisely the regular languages, thus providing an alternative way to present these languages. A remarkable consequence of this kind of recognition is that it induces a partition of the language into its cross-sections, where the $n$th cross-section contains all the words of length $n$ in the language. Finally, we show how to use linear recurrence equations to calculate the density function of a regular language, which assigns to every $n$ the number of words of length $n$ in the language. We also show how to count the number of successful paths of a weighted automaton.
Babaali Parisa
Carta-Gerardino Edoardo
No associations
LandOfFree
Weighted Automata and Recurrence Equations for Regular Languages does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Weighted Automata and Recurrence Equations for Regular Languages, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Weighted Automata and Recurrence Equations for Regular Languages will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-344883