It is worth noting that a machine with no accepting states does not accept any string as part of the language (not even the empty string) - it is essentially the Empty Language, ∅. If the machine has only 1 accepting state, it is oftentimes named with the letter A. Common ways include bolding or underlining the name, or using a double circle instead of a single. Graphically, accepting states are indicated distinctly from other states in any of a number of ways. Throughout this course we will exclusively use the term Accepting because I think it is a more descriptive term, but be aware that other places will use the term Final to mean the same thing. Accepting State or Final State - A set of states which the machine may halt in, provided it has no input left, in order to accept the string as part of the language.Graphically, the start state is represented as a state with an unlabeled arrow pointing from nothing to it. The name for the start state will usually either be S or, canonically, q 0 (it is numbered with the lowest number of all the states). It is the state that the machine naturally starts in before it reads any input. Start State - For programmers, this is known as the program entry point.Graphically, states are represented by a circle with the name inside. Canonical names for states (which we will get to later) commonly consist of the lowercase letter 'q' followed by a number, e.g. State - A resting place while the machine reads more input, if more input is available.Later, we will introduce machines capable of generating an output string to return in addition to its standard return value. Initially, this will either be accepted or rejected, indicating whether the input string is respectively part of the language or not. Return - The results of running the machine on a given input.An input is read by a machine in a forward fashion, one symbol at a time. it doesn't make sense to feed a 3 to a machine that only reads 0's and 1's). The string must only be made up of symbols from the machine's alphabet (e.g. Input - A string fed to a machine which the machine will determine whether it is part of the language that the machine was designed for.Overall, it is in these chapters that the uniqueness of the book begins to shine, as the algorithms are presented starting from the theoretical automaton operation at their core, then illustrated by constructing the relevant automata, and finally exemplified with code snippets in Pynini. One possible complaint is that the discussion of a few of these algorithms could have been improved with a step-by-step example of the procedure, although examples of these can be easily found in other resources. The optimization section comes with a nice practical example from speech recognition, and speech serves as a good motivation to lead into algorithms to compute shortest distance and shortest paths. Chapter 4 presents slightly more advanced algorithms, focusing, for example, on the problem of optimization. The generalization of each algorithm from finite-state machines to weighted finite-state machines is also highlighted. Chapter 3 focuses on essential operations such as concatenation, closure, union, composition, and so forth. However, the chapter lays down these theoretical notions clearly, and its stands as an intriguing starting point for any reader interested in learning more about the mathematics of monoids and formal languages.Ĭhapters 3 and 4 are a walkthrough of key algorithms for finite-state machines. Unsurprisingly, this section is the densest part of the chapter and it could have benefitted from an explanation of the intuition behind the connection between wellformedness of a string, recognition by an automaton, and paths over semirings-especially considering how relevant such concepts become when the book transitions into its algorithmic parts. This is a welcome choice that makes the book somewhat unique among introductory/application-oriented materials on these topics. Weighted finite-state automata play a prominent role in the book and the authors introduce them algebraically through the notion of semiring (Pin 1997). The chapter balances intuitive explanations of technical concepts without sacrificing formal rigor, in particular in the presentation of finite-state automata/transducers and their formal definitions. Chapter 1 provides an accessible introduction to formal languages and automata theory, starting with a concise but helpful historical review of the development of finite-state technologies and their ties to linguistics.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |