Grammatical Inference in Chomsky Hierarchy for Regular Language and Context Free Language

Abstract

Grammatical inference or grammar induction aims to find underlying newlineautomaton or production rules from the given observations to represent unknown target newlinelanguage. The given observations may be in the form of text (strings), trees or graphs. The newlinelearner (Inference machine or learning algorithm) has to identify the underlying automaton newlineor supporting grammar from the given set of observations so that it will conveniently newlinemodel the unseen data. The input observations are normally composed of a finite number newlineof alphabets; Grammatical inference theory and grammar learning have potential newlineapplications in Machine learning where many learning algorithms are proposed to check newlinethe validity of the unknown grammar or automaton. Grammatical inference theory has newlineapplications in various engineering fields like pattern recognition, computational newlinelinguistics, natural language processing, computational biology and many more. newlineGrammatical inference analyses various levels of Chomsky hierarchy newline