Context-free recognition with weighted automata

Corinna Cortes, Mehryar Mohri

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)133-150
Number of pages18
JournalGrammars
Volume3
Issue number2-3
StatePublished - 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

Fingerprint Dive into the research topics of 'Context-free recognition with weighted automata'. Together they form a unique fingerprint.

Cite this