## Abstract

We introduce the definition of language recognition with weighted automata, a generalization of the classical definition of recognition with unweighted acceptors. We show that, with our definition of recognition, weighted automata can be used to recognize a class of languages that strictly includes regular languages. The class of languages accepted depends on the weight set which has the algebraic structure of a semiring. We give a generic linear time algorithm for recognition with weighted automata and describe examples with various weight sets illustrating the recognition of several classes of context-free languages. We prove, in particular, that the class of languages equivalent to the language of palindromes can be recognized by weighted automata over the (+, ·)-semiring, and that the class of languages equivalent to the Dyck language of first order D′_{1}* can be recognized by weighted automata over the real tropical semiring. We also prove that weighted automata over the real tropical semiring can be used to recognize regular expressions.

Original language | English (US) |
---|---|

Pages (from-to) | 133-150 |

Number of pages | 18 |

Journal | Grammars |

Volume | 3 |

Issue number | 2-3 |

State | Published - 2000 |

## Keywords

- Context-free languages
- Context-free recognition
- Finite automata
- Finite-state transducers
- Rational power series
- Weighted automata

## ASJC Scopus subject areas

- Management of Technology and Innovation