# US 8,543,383 B2 · Systems and methods for generating weighted finite-state automata representing grammars > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,543,383 B2 - Document ID: US8543383B2 - Status: Granted - Kind: B2 - Application number: 13/284,111 - Filed: 2011-10-28 - Published: 2012-02-23 - Granted: 2013-09-24 - Earliest claimed: 2002-01-07 - Assignees: AT&T Intellectual Property II, L.P. - Applicants: Mehryar Mohri; Mark-Jan Nederhof - Inventors: Mehryar Mohri; Mark-Jan Nederhof - Web page: https://patentgrep.com/patent/US8543383B2 ## CPC - G10L 15/193: Formal grammars, e.g. finite state automata, context free grammars or word networks - G06F 40/289: Phrasal analysis, e.g. finite state techniques or chunking - G10L: SPEECH ANALYSIS TECHNIQUES OR SPEECH SYNTHESIS; SPEECH RECOGNITION; SPEECH OR VOICE PROCESSING TECHNIQUES; SPEECH OR AUDIO CODING OR DECODING - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract 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. ## Claims ### Claim 1 A method comprising: generating a first finite-state automaton from a set of rules associated with a context-free grammar; generating a second finite-state automaton based on the first finite-state automaton, wherein the second finite-state automaton defines a delayed acceptor for a plurality of non-terminal symbols of the context-free grammar; generating a third finite-state automaton associated with a topology of the context-free grammar as the context-free grammar is applied to an input string of symbols, wherein the topology defines an application of the context-free grammar; and modifying, via a processor, the third finite-state automaton by: identifying, for each edge of a plurality of edges of the third finite-state automaton, a non-terminal symbol of the plurality of non-terminal symbols; and replacing the each edge of the plurality of edges of the third finite-state automaton with an edge of the second finite-state automaton based on the non-terminal symbol for each edge. ### Claim 2 (depends on 1) The method of claim 1, wherein each edge of the plurality of edges extends between an initial state and a final state, wherein the initial state and the final state are defined based on the topology. ### Claim 3 (depends on 2) The method of claim 2, wherein the topology further identifies a constraint on the context-free grammar. ### Claim 4 (depends on 1) The method of claim 1, wherein the context-free grammar has non-terminal symbols and terminal symbols. ### Claim 5 A system comprising: a processor; and a computer-readable medium having instructions stored which, when executed by the processor, cause the processor to perform operations comprising: generating a first finite-state automaton from a set of rules associated with a context-free grammar; generating a second finite-state automaton based on the first finite-state automaton, wherein the second finite-state automaton defines a delayed acceptor for a plurality of non-terminal symbols of the context-free grammar; generating a third finite-state automaton associated with a topology of the context-free grammar as the context-free grammar is applied to an input string of symbols, wherein the topology defines an application of the context-free grammar; and modifying the third finite-state automaton by: identifying, for each edge of a plurality of edges of the third finite-state automaton, a non-terminal symbol of the plurality of non-terminal symbols; and replacing the each edge of the plurality of edges of the third finite-state automaton with an edge of the second finite-state automaton based on the non-terminal symbol for each edge. ### Claim 6 (depends on 5) The system of claim 5, wherein each edge of the plurality of edges extends between an initial state and a final state, and wherein the initial state and the final state are defined based on the topology. ### Claim 7 (depends on 6) The system of claim 6, wherein the topology further identifies a constraint on the context-free grammar. ### Claim 8 (depends on 5) The system of claim 5, wherein the context-free grammar has non-terminal symbols and terminal symbols. ### Claim 9 A non-transitory computer-readable storage medium having instructions stored which, when executed by a computing device, cause the computing device to perform operations comprising: generating a first finite-state automaton from a set of rules associated with a context-free grammar; generating a second finite-state automaton based on the first finite-state automaton, wherein the second finite-state automaton defines a delayed acceptor for a plurality of non-terminal symbols of the context-free grammar; generating a third finite-state automaton associated with a topology of the context-free grammar as the context-free grammar is applied to an input string of symbols, wherein the topology defines an application of the context-free grammar; and modifying the third finite-state automaton by: identifying, for each edge of a plurality of edges of the third finite-state automaton, a non-terminal symbol of the plurality of non-terminal symbols; and replacing the each edge of the plurality of edges of the third finite-state automaton with an edge of the second finite-state automaton based on the non-terminal symbol for each edge. ### Claim 10 (depends on 9) The non-transitory computer-readable storage medium of claim 9, wherein each edge of the plurality of edges extends between an initial state and a final state, and wherein the initial state and the final state are defined based on the topology. ### Claim 11 (depends on 10) The non-transitory computer-readable storage medium of claim 10, wherein the topology further identifies a constraint on the context-free grammar. ### Claim 12 (depends on 9) The non-transitory computer-readable storage medium of claim 9, wherein the context-free grammar has non-terminal symbols and terminal symbols.