Grammatical Inference

AKA: Grammar Induction, Grammar Learning, Grammar Inference.
Example(s):
- …
Counter-Example(s):
- Morphological Analysis,
- Word Sense Disambiguation.
See: Finite State Machine, Machine Learning, Formal Grammar, Context-Free Grammar, Grammar, Production Rules.

References

(Wikipedia, 2018) ⇒ https://en.wikipedia.org/wiki/Grammar_induction Retrieved:2018-4-29.
- Grammar induction (or grammatical inference^[1] ) is the process in machine learning of learning a formal grammar (usually as a collection of re-write rules or productions or alternatively as a finite state machine or automaton of some kind) from a set of observations, thus constructing a model which accounts for the characteristics of the observed objects. More generally, grammatical inference is that branch of machine learning where the instance space consists of discrete combinatorial objects such as strings, trees and graphs.

(Saitta & Sebag, 2017) ⇒ Saitta L., Sebag M. (2017) "Grammatical Inference". In: Sammut C., Webb G.I. (eds) Encyclopedia of Machine Learning and Data Mining. Springer, Boston, MA
- QUOTE: Grammatical inference is concerned with inferring grammars from positive (and possibly negative) examples (Angluin 1978; Korfiatis and Paliouras 2008; Sakakibara 2005). A context-free grammar (CFG) (...)

(Saitta; Michele Sebag, 2011) ⇒ Lorenza Saitta; Michele Sebag. (2011). “Grammatical Interface.” In: (Sammut & Webb, 2011) p.569
- QUOTE: Grammatical inference is concerned with inferring grammars from positive (and possibly negative) examples (Angluin 1978; Korfiatis and Paliouras 2008; Sakakibara 2005). A context-free grammar (CFG) [math]\displaystyle{ \mathcal{G} }[/math] (equivalent to a push-down finite-state automaton) is described by a four tuple [math]\displaystyle{ (\mathcal{Q},\varepsilon, \delta, \Sigma) }[/math]:
  - [math]\displaystyle{ \mathcal{\Sigma} }[/math], is the alphabet of terminal symbols, upon which the grammar is defined.
  - The pair [math]\displaystyle{ (\mathcal{Q},\varepsilon) }[/math] defines a graph, where [math]\displaystyle{ \mathcal{Q} }[/math] is the set of nodes (states), and [math]\displaystyle{ \varepsilon }[/math] is the set of edges (production rules). [math]\displaystyle{ \mathcal{Q} }[/math] includes one starting node [math]\displaystyle{ q_0 }[/math] and a set [math]\displaystyle{ \mathcal{Q_f} (\mathcal{Q_f} \in \mathcal{Q}) }[/math] of final or accepting nodes.
  - (...)