首页>
外国专利>
Systems and methods for generating weighted finite-state automata representing grammars
Systems and methods for generating weighted finite-state automata representing grammars
展开▼
机译:用于生成表示语法的加权有限状态自动机的系统和方法
展开▼
页面导航
摘要
著录项
相似文献
摘要
A context-free grammar can be represented by a weighted finite-state transducer. This representation can be used to efficiently compile that grammar into a weighted finite-state automaton that accepts the strings allowed by the grammar with the corresponding weights. The rules of a context-free grammar are input. A finite-state automaton is generated from the input rules. Strongly connected components of the finite-state automaton are identified. An automaton is generated for each strongly connected component. A topology that defines a number of states, and that uses active ones of the non-terminal symbols of the context-free grammar as the labels between those states, is defined. The topology is expanded by replacing a transition, and its beginning and end states, with the automaton that includes, as a state, the symbol used as the label on that transition. The topology can be fully expanded or dynamically expanded as required to recognize a particular input string.
展开▼