Canonical Context-Free Grammars and Strong Learning: Two Approaches
Alexander Clark · 2015
Strong learning of context-free grammars is the problem of learning a grammar which is not just weakly equivalent to a target grammar but isomorphic or structurally equivalent to it.This is closely related to the problem of defining a canonical grammar for the language.The current proposal for strong learning of a small class of CFGs uses grammars whose nonterminals correspond to congruence classes of the language, in particular to a subset of those that satisfy a primality condition.Here we extend this approach to larger classes of CFGs where the nonterminals correspond instead to closed sets of strings; to elements of the syntactic concept lattice.We present two different classes of canonical context-free grammars.One is based on all of the primes in the lattice: the other, more suitable for strong learning algorithms is based on a subset of primes that are irreducible in a certain sense.* ⇒ λ.Now Y ∈ Γ(X) so there is some production X → α such that ᾱ ⊇ Y .Now if α = Z 1 . . .Z k then each of the Z i must be a proper subset of X that contains λ, (since λ ∈ Y ⊆ ᾱ).Since they are proper subsets we have Z i * ⇒ λ and thusProof.We use just the same argument as the previous proof, except that when we consider α = Z 1 . . .Z k , there must be at least one i such that a ∈ Z i and λ ∈ Z j for all j = i.By Lemma 9, Z j * ⇒ λ, by minimality of the counterexample Z i * ⇒ a, and therefore X * ⇒ a.Lemma 11.For any w = a 1 . . .a n ∈ {l r} for some l r, there are A 1 , . . ., A n ∈ V such that a i ∈ A i , and A 1 . . .A n ⊆ {l r} .