Generating Context-Free Grammars using Classical Planning

1 Introduction

A formal grammar is a set of symbols and rules that describe how to form the strings of certain formal language. Usually two tasks are defined over formal grammars:

• Production: Given a formal grammar, generate strings that belong to the language represented by the grammar.
• Recognition (also known as parsing): Given a formal grammar and a string, determine whether the string belongs to the language represented by the grammar.

Chomsky defined four classes of formal grammars that differ in the form and generative capacity of their rules [Chomsky, 2002]. In this paper we focus on Context-Free Grammars (CFGs), where the left-hand side of a grammar rule is always a single non-terminal symbol. This means that the symbols on the left-hand side of CFG rules do not appear in the strings that belong to the corresponding language.

To illustrate this Figure 1(a) shows an example CFG that contains a single non-terminal symbol, S, and three terminal symbols (a, b and ϵ, where ϵ denotes the empty string). This CFG defines three production rules that can generate, for instance, the string aabbaa by applying the first rule twice, then the second rule once and finally, the third rule once again. The parse tree in Figure 1(b) exemplifies the previous rule application and proves that the string aabbaa belongs to the language defined by the grammar.

Learning the entire class of CFGs using only positive examples, i.e. strings that belong to the corresponding formal language, is not identifiable in the limit [Gold, 1967]. In this paper we address the generation of CFGs from positive examples but: (1) for a bounded maximum number of non-terminal symbols in the grammar and (2), a bounded maximum size of the rules in the grammar (i.e. a maximum number of symbols in the right-hand side of the grammar rules).

Our approach is compiling this inductive learning task into a classical planning task whose solutions are sequences of actions that build and validate a CFG compliant with the input strings. The reported empirical results show that our compilation can generate CFGs from small amounts of input data (even a single input string in some cases) using an off-theshelf classical planner. In addition, we show that the compilation is also suitable for implementing the two canonical tasks of CFGs, string production and string recognition.

2 Background

This section defines the formalization of CFGs and the planning models that we adopt in this work.

2.1 Context-Free Grammars

We define a CFG as a tuple G = 〈V, v0, Σ, R〉 where:

• V is the finite set of non-terminal symbols, also called variables. Each v ∈ V represents a sub-language of the language defined by the grammar.
• v0 ∈ V is the start non-terminal symbol that represents the whole grammar.
• Σ is the finite set of terminal symbols, which are disjoint from the set of non-terminal symbols, i.e. V ∩ Σ ̸= ∅. The set of terminal symbols is the alphabet of the language defined by G and can contain the empty string, which we denote by ϵ ∈ Σ.

• R : V → (V ∪Σ)∗ is the finite set of production rules in the grammar. By definition rules r ∈ R always contain a single non-terminal symbol on the left-hand side.

Figure 1(a) shows a 1-variable CFG since it defines a single non-terminal symbol. In this example V = {S}, v0 = S, Σ = {a, b, ϵ}, and R = {S → aSa, S → bSb, S → ϵ}.

For any two strings e1, e2 ∈ (V ∪ Σ)∗ we say that e1 directly yields e2, denoted by e1 ⇒ e2, iff there exists a rule α → β ∈ R such that e1 = u1αu2 and e2 = u1βu2 with u1, u2 ∈ (V ∪ Σ)∗ . Furthermore we say e1 yields e2, denoted by e1 ⇒∗ e2, iff ∃k ≥ 0 and ∃u1, . . . , uk such that e1 = u1 ⇒ u2 ⇒ . . . ⇒ uk = e2. For instance, Figure 1(b) shows how the string S yields the string aabbaa. The language of a CFG, L(G) = {e ∈ Σ∗ : v0 ⇒∗ e}, is the set of strings that contain only terminal symbols and that can be yielded from the string that contains only the initial non-terminal symbol v0.

Given a CFG G and a string e ∈ L(G) that belongs to its language, we define a parse tree tG,e as an ordered, rooted tree that determines a concrete syntactic structure of e according to the rules in G:

• Each node in a parse tree tG,e is either:
• An internal node that corresponds to the application of a rule r ∈ R.
• A leaf node that corresponds to a terminal symbol σ ∈ Σ and has no outgoing branches.
• Edges in a parse tree tG,e connect non-terminal symbols to terminal or non-terminal symbols following the rules R in G.

2.2 Classical Planning with Conditional Effects

We use the model of classical planning with conditional effects because conditional effects allow to adapt the execution of a sequence of actions to different initial states, as shown in conformant planning [Palacios and Geffner, 2009]. The support of conditional effects is now a requirement of the International Planning Competition [Vallati et al., 2015] and most current classical planners natively cope with conditional effects without compiling them away [Helmert, 2006].

We use F to denote a set of propositional variables or fluents describing a state. A literal l is a valuation of a fluent f ∈ F, i.e. l = f or l = ¬f. A set of literals L on F represents a partial assignment of values to fluents (WLOG we assume that L does not assign conflicting values to any fluent). We use L(F) to denote the set of all literal sets on F, i.e. all partial assignments of values to fluents. Given L, let ¬L = {¬l : l ∈ L} be the complement of L.

A state s is a set of literals such that |s| = |F|, i.e. a total assignment of values to fluents. The number of states is then 2|F| . Explicitly including negative literals ¬f in states simplifies subsequent definitions, but we often abuse notation by defining a state s only in terms of the fluents that are true in s, as is common in STRIPS planning.

A classical planning frame is a tuple Φ = 〈F,A〉, where F is a set of fluents and A is a set of actions with conditional effects. Each action a ∈ A has a set of literals pre(a) ∈ L(F) called the precondition and a set of conditional effects cond(a). Each conditional effect C ▷E ∈ cond(a) is composed of two sets of literals C ∈ L(F) (the condition) and E ∈ L(F) (the effect).

An action a ∈ A is applicable in state s if and only if pre(a) ⊆ s, and the resulting set of triggered effects is

i.e. effects whose conditions hold in s. The result of applying a in s is a new state θ(s, a) = (s \ ¬eff(s, a)) ∪ eff(s, a).

Given a frame Φ = 〈F,A〉, a classical planning instance is a tuple P = 〈F,A, I,G〉, where I ∈ L(F) is an initial state (i.e. |I| = |F|) and G ∈ L(F) is a goal condition. We consider the fragment of classical planning with conditional effects that includes negative conditions and goals.

A plan for P is an action sequence π = 〈a1, . . . , an〉 that induces a state sequence 〈s0, s1, . . . , sn〉 such that s0 = I and, for each i such that 1 ≤ i ≤ n, ai is applicable in si-1 and generates the successor state si = θ(si-1, ai). The plan π solves P if and only if G ⊆ sn, i.e. if the goal condition is satisfied following the application of π in I.

2.3 Generalized Planning

Our approach for learning CFGs from positive examples is to model this task as a generalized planning problem that is eventually solved with an off-the-shelf classical planner using the compilation proposed by Jim´enez and Jonsson (2015).

We define a generalized planning problem as a finite set of classical planning instances P = {P1, . . . , PT} within the same planning frame Φ. Therefore, P1 = 〈F, A, I1, G1〉, . . . , PT = 〈F, A, IT , GT 〉 share the same fluents and actions and differ only in the initial state and goals. Although actions are shared, each action can have different interpretations in different states due to conditional effects. Given a planning frame Φ = 〈F,A〉, then Γ(Φ) = {〈F,A, I,G〉 : I ∈ L(F), |I| = |F|,G ∈ L(F)} denotes the set of all planning instances that can be instantiated from Φ by defining an initial state I and a goal condition G.

A solution Π to a generalized planning problem P is a generalized plan that solves every individual instance Pt, 1 ≤ t ≤ T. Generalized plans may have diverse forms that range from DS-planners [Winner and Veloso, 2003] and generalized polices [Mart´ın and Geffner, 2004] to finite state machines [Bonet et al., 2010; Segovia-Aguas et al., 2016b], AND/OR graphs or CFGs [Ramirez and Geffner, 2016].

In this work we assume that the solution to a generalized planning problem P is in the form of a planning program [Jim´enez and Jonsson, 2015; Segovia-Aguas et al., 2016a]. Briefly, a planning program is a set of procedures, each a sequence of planning actions enhanced with goto instructions and procedure calls. However, in this work there is no need to include goto instructions since they are not needed to represent CFGs.

Given a frame Φ = 〈F, A〉, a planning program with procedures is a finite set of planning programs Π = {Π0, . . . , Πm} (we adopt the convention of designating Π0 as the main program, and {Π1, . . . ,Πm} as the auxiliary procedures). Every Πj, 0 ≤ j ≤ m is then a sequence of instructions

Π0: 0. produce a Π1: 0. produce b

1. produce a

1. produce b

2. call(1)

2. end

3. produce a

4. produce a

5. end

Figure 2: Example of a planning program Π = {Π0, Π1} with one auxiliary procedure that produces the string aabbaa.

Πj = 〈w0, . . . ,wn〉. Each instruction wi, 0 ≤ i ≤ n, is associated with a program line i and is drawn from the instructions set I = A ∪ Icall ∪ {end}, where Icall = {call(j') : 0 ≤ j ′ ≤ m} is the set of procedure calls, allowing any procedure to call any other procedure on an arbitrary program line (j = j ′ implies a recursive call). Figure 2 shows an example of a planning program with one auxiliary procedure that produces the string aabbaa. In this example, A = {produce a, produce b}, where produce a has the effect of producing the terminal symbol a.

To define the execution model of a planning program with procedures we first introduce the notion of a call stack that keeps track of where control should return when the execution of a procedure terminates. Each element of the call stack is a tuple (j, i), where j is an index that refers to a procedure Πj, 0 ≤ j ≤ m and i is a program line, 0 ≤ i ≤ |Πj|. In what follows we use Ω ⊕ (j, i) to denote a call stack recursively defined by a call stack Ω and a top element (j, i).

The execution model for a planning program Π consists of a program state (s, Ω), where s is a planning state and Ω is a call stack. Given a program state (s, Ω⊕(j, i)), the execution of instruction wj i on line i of procedure Πj is defined as:

• If wj i ∈ A, the new program state is (s′ , Ω ⊕ (j, i + 1)), where s′ = θ(s, wj i ) is the state resulting from applying action wj i in state s.
• If wj i = call(j'), the new program state is (s,Ω ⊕ (j, i + 1) ⊕ (j ′ , 0)). In other words, calling a procedure Πj ′ has the effect of (1) incrementing the program line at the top of the stack; and (2) pushing a new element onto the call stack to start the execution of Πj ′ on line 0.
• If wj i = end, the new program state is (s,Ω), i.e. has the effect of terminating a procedure by popping element (j, i) from the top of the call stack.

The execution of a planning program with procedures terminates when executing an end instruction empties the call stack, i.e. in program states (s, ∅).

To execute a planning program with procedures Π on a planning problem P = 〈F,A, I,G〉, we set the initial program state to (I, (0, 0)), i.e. execution is in the initial planning state, on program line 0 of the main program Π0. To ensure that the execution model remains bounded we impose an upper bound ℓ on the size of the call stack.

Executing Π on P can fail for any of these four reasons:

1. Execution terminates in program state (s, ∅) but the goal condition does not hold, i.e. G ̸⊆ s.
2. When executing action wi ∈ A in program state (s, Ω), the precondition of wi does not hold, i.e. pre(wi) ̸⊆ s.
3. Execution enters an infinite loop that never reaches a program state (s, ∅).
4. Executing a call(j') instruction in program state (s,Ω) exceeds the stack size |Ω| = ℓ, i.e. causes a stack overflow.

We say that Π solves P iff the goal condition holds when the execution of Π on P terminates, i.e. (s, ∅)∧G ⊆ s. Given a generalized planning problem P = {P1, . . . , PT }, a planning program Π solves P iff Π solves each planning instance Pt, 1 ≤ t ≤ T .

2.4 Computing Planning Programs

A classical planner can detect the four failure conditions defined above, making it particularly suitable for generating planning programs. We briefly describe here the compilation from generalized planning to classical planning for computing planning programs [Jim´enez and Jonsson, 2015; Segovia-Aguas et al., 2016a].

Given a generalized planning problem P = {P1, . . . , PT }, the bounds on the number of program lines n, auxiliary procedures m and stack size ℓ, the compilation outputs a classical planning problem P ℓn,m = 〈F ℓn,m,Aℓn,m, I ℓn,m,Gℓn,m〉 such that any classical plan π that solves P ℓn,m programs the instructions of a planning program Π and simulates the execution of Π on each P1≤t≤T , validating that Π solves P.

In more detail, the set of fluents F ℓn,m extends F with:

• F ℓ pc = {pcki : 0 ≤ i ≤ n, 1 ≤ k ≤ ℓ} ∪ {prockj : 0 ≤ j ≤ m, 1 ≤ k ≤ ℓ} representing the current line and procedure.
• F ℓ top = {topk }0≤k≤ℓ representing the top level of the stack at the current time.
• F m ins encoding the instructions in the main and auxiliary procedures, which is formally defined as F m ins = {insi,j,w : 0 ≤ i ≤ n, 0 ≤ j ≤ m,w ∈ A ∪ Icall ∪ {nil, end}}, where nil indicates that the instruction on line i of procedure j is empty, i.e. can be programmed.
• done, a fluent marking we are done programming and executing the planning program.

Aℓn,m defines the following actions:

• An action wk i,j for each action instruction w ∈ A, program line i, procedure j and stack level k:

• An action callj ′ ,k i,j for each call(j') ∈ Icall that pushes a new program line (j ′ , 0) onto the stack:

• Actions endk+1 i,j that simulate the termination on line i of procedure j on stack level k + 1, 0 ≤ k < ℓ:

The effect is to pop the program line (j, i) from the top of the stack.

The action set Aℓn,m contains the following actions:

• For each instruction wk i,j , w ∈ A ∪ Icall ∪ {end}, an action P(wk i,j ) that programs w, and a repeat action R(wk i,j ) that executes w when already programmed:

• For each planning problem Pt, 1 ≤ t ≤ T , a termination action termt that simulates the successful termination of the planning program on Pt when the stack is empty:

Note that the effect of termt, t < T, is to reset the program state to the initial state of problem Pt+1.

The initial state sets all the program lines (main and auxiliary procedures) as empty and sets the procedure on stack level 1 to Π0 (the main procedure) with the program counter pointing to the first line of that procedure. The initial state on fluents in F is I1, hence I ℓn,m = I1 ∪ {insi,j,nil : 0 ≤ i ≤ n, 0 ≤ j ≤ m} ∪ {top1 , pc10 , proc10 }. The goal condition is defined as Gℓn,m = {done}.

3 Generating Context-Free Grammars

This section explains our approach to generating CFGs from input strings using classical planning. We formalize this task as a tuple 〈Σ, E, m〉, where:

• Σ is the finite set of terminal symbols.
• E = {e1, . . . , eT} is the finite set of input strings containing only terminal symbols: et ∈ Σ∗ , 1 ≤ t ≤ T .
• m is a bound on the number of non-terminal symbols Vm = {v0, . . . , vm}. As a consequence, m implicitly defines the space of possible rules, Vm → (Vm ∪ Σ)∗ .

A solution to this inductive learning task is a CFG G = 〈Vm, v0,Σ,Rm〉 such that, for every e ∈ E, there exists a parse tree tG,e.

Π0: 0. choose(1|5|8)

1. parse a

2. call(0)

3. parse a

4. end

5. parse b

6. call(0)

7. parse b

8. end

Figure 3: Planning program that represents the CFG in Figure 1(a).

3.1 CFGGeneration as Generalized Planning

Our approach for solving 〈Σ, E, m〉 is modeling this task as a generalized planning task P = {P1, . . . , PT } where each input string et ∈ E corresponds to an individual classical planning task Pt ∈ P such that 1 ≤ t ≤ T and Pt = 〈F, A, It, Gt〉 is defined as follows:

• F comprises the fluents for modeling input strings as lists of symbols. These fluents are string(id, σ) and next(id, id2), where 0 ≤ id, id2 ≤ z, σ ∈ Σ and z is a bound on the string length. For instance, the string abba is encoded as:

string(i0, a), string(i1, b), string(i2, b), string(i3, a), next(i0, i1), next(i1, i2), next(i2, i3), next(i3, i4).

In addition, F includes fluents pos(id), 0 ≤ id ≤ z, to indicate the current string position, and symb(σ), σ ∈ Σ, to indicate the symbol at the current string position.

• A contains the actions for parsing the current symbol of an input string. There is a parseσ action for each symbol σ ∈ Σ, e.g. A = {parsea, parseb} for the CFG of Figure 1(a). Action parseσ recognizes that σ is at the current position of the string and advances the position.

• It contains the fluents encoding the t-th string, et ∈ E, and its initial position pos(0).
• Gt requires that et is parsed, i.e. Gt = {pos(|et|)}.

According to this definition, a solution to a generalized planning problem P that models a CFG generation task 〈Σ, E, m〉 parses every et ∈ E.

3.2 Computing CFGs with Classical Planning

To compute CFGs with classical planning we first extend the planning program formalism, so that it can represent CFGs. Then we adapt the generalized planning compilation for computing the extended planning programs with an off-the-shelf classical planner.

Our extension of the planning program formalism augments its instruction set I with choice instructions. Choice instructions are intended to jump to a target line of a planning program and are defined as Ichoice = {choose(Target)}, where Target ⊆ {1, . . . , n} is a subset of possible target program lines. Figure 3 shows a planning program with a choice instruction that encodes the CFG in Figure 1(a). In this example instruction choose(1|5|8) represents a jump to one of these three possible targets, line 1, line 5 or line 8.

The execution model for planning programs with choice instructions behaves as explained in Section 2.3. The conditions for termination and success are the same as in the original planning program formalism. The only new behavior that has to be defined is the execution of choice instructions. The execution of an instruction wj i = choose(Target) on line i of procedure Πj actively chooses to jump to a new line i′ ∈ Target, changing the program state from (s, Ω ⊕ (j, i)) to (s, Ω ⊕ (j, i′ )).

The representation of CFGs with planning programs is done associating each non-terminal symbol vj ∈ Vm with a planning program Πj. Choice instructions always appear on the first line of Πj and represent possible jumps to the lines coding the grammar rules, vj → (vj ∪ Σ)∗ , associated to the corresponding non-terminal symbol. Initially, the subset of target program lines only includes 1 and n, i.e. choose(1|8) for the example in Figure 3. Whenever we program an end instruction on a line i, we add i+1 to the subset of target lines, leading to the choice instruction choose(1|5|8) in Figure 3.

The compilation takes as input a CFG generation task 〈Σ,E,m〉 such that |et| ≤ z for each et ∈ E, a number of program lines n and a stack size ℓ, and outputs a classical planning instance P ℓ,z n,m = 〈F ℓ,z n,m, Aℓ,z n,m, I ℓ,z n,m, Gℓ,z n,m〉. The compilation is almost identical to the compilation described in the previous section; the only relevant difference is that Aℓ,z n,m includes actions for simulating the execution of choice

Lemma 1. Any classical plan π that solves P ℓ,z n,m induces a valid model G = 〈Vm, v0,Σ,Rm〉 for the CFG generation task 〈Σ, E, m〉.

Proof sketch. Once the instructions of a planning program Π = {Π0, . . . ,Πm} are programmed they can only be executed. The classical plan π has to program the instructions (if not yet programmed) of Π and simulate its execution, actively choosing the jumps defined by the choice instructions and their corresponding subsets of target lines. This simulation is done for the planning task Pt encoding the t-th string in E and the active choice corresponds exactly to the construction of the parse tree for the t-th string. If this is done for every 1 ≤ t ≤ T , the CFG induced by π satisfies the solution condition for the solutions of the CFG generation task 〈Σ, E, m〉.

3.3 Parsing and Production with Planning

String production and string parsing for arbitrary CFGs can also be addressed using our compilation and an off-the-shelf classical planner.

Parsing. Let e /∈ E be a new string, and let Pe = 〈F ℓ,z n,m, Aℓ,z n,m, Ie,Ge〉 be the classical planning instance for parsing the string e, i.e. instantiated on the planning frame as the problem P ℓ,z n,m. In this case we can use a classical planner to determine whether e ∈ L(G).

Our approach is to specify G in the initial state of Pe, making initially true the fluents insi,j,w that correspond to the planning program that encodes G, and ignoring the actions P (wk i,j ) for programming instructions. A solution plan πe to Pe is then constrained to the actions that execute the instructions specified by G and represents a parse tree tG,e. Essentially, parsing consists in correctly choosing the target program line i′ each time a choice instruction is executed.

Interestingly parsing can also be understood as activity recognition using plan libraries that are in the form of CFGs [Ramirez and Geffner, 2016].

Production. We can produce a string e ∈ L(G) using our compilation and an off-the-shelf classical planner.

Again we use a classical planning instance Pe that represents the parsing of example e with G also specified in the initial state of Pe and ignoring the actions for programming instructions. The difference with the previous task is that here the linked list that encodes the string e is initially empty (the corresponding fluents are false at Ie). This list is filled up, symbol by symbol, by the actions that execute G until reaching the end of the string. To do so actions parseσ are replaced with actions produceσ that add symbol σ ∈ Σ at the current position of the string. Formally, produceσ is defined as:

where active is a fluent that keeps track of whether we have reached the end of the string to be generated.

Text production using grammars and classical planning is a well studied task [Schwenger et al., 2016; Koller and Hoffmann, 2010]. This task is also related to the compilation of domain-specific control knowledge for planning [Baier et al., 2007; Alford et al., 2009].

4 Evaluation

We designed two types of experiments: (1) Generation, for computing CFGs compliant with a set of input strings and (2), Recognition for parsing unseen input strings given a CFG. All the experiments are run on an Intel Core i5 3.10 GHz x 4 with 4 GB of RAM, using the classical planner Fast Downward [Helmert, 2006], with the LAMA-2011 configuration, and a planning time limit of 600 seconds.

We created six domains that correspond to CFGs with different structure and alphabet. The domain AnBn corresponds to the AnBn language. The Parenthesis domain corresponds to the strings that can be formed following one of two wellbalanced parenthesis distributions, sequential ()() . . . or enclosing ((. . .)). Parenthesis Multiple corresponds to the enclosing well-balanced parenthesis distribution but using a larger alphabet, Σ = {(, {, [, ], }, )}. In the Binary Arithmetics domain the alphabet contains two possible binary values {0, 1} and two operators {+,-}, and corresponds to the language of the arithmetic expressions composed by an arbitrary binary number, an operator and another binary number. For Arithmetics the alphabet includes the values {0, . . . , 9} and the operators {+,-, ∗, /}, and the language is the set of expressions formed as decimal number, operator and decimal number. Finally, a simplified English Grammar that includes Sentence, Noun Phrase and Verb Phrase as nonterminal symbols while adjective, adverb, noun and verb are terminal symbols.

Table 1 shows the results of the Generation tasks. For each domain we report the number m of non-terminal symbols, the size of the stack, the procedure lines (per non-terminal symbol), the number of input strings (per non-terminal symbol) and the planning time for computing each procedure corresponding to a non-terminal symbol.

The Generation results show that non-terminal symbols are used with two aims: i) abstracting a set of terminal symbols, e.g. the first procedure of the Arithmetics domain (with 20 lines, learned from 10 strings in 10.3 seconds) processes any digit in the set {0, . . . , 9}; ii) grouping multiple rules, e.g. in English Grammar one procedure represents a Noun Phrase (NP) that is composed of one or more adjectives (a) and a noun (n), so it computes the rules NP → an|aNP .

Table 2 shows the results for the Recognition tasks. In these experiments the CFGs grammars are given so we explore the performance of our approach using larger stack sizes. For each domain we report the size of the stack (which limits the max depth of the possible parse trees), the number of strings, and the total planning time required for parsing the strings.

5 Related work

The learning of CFGs can also be understood in terms of activity recognition, such that the library of activities is formalized as a CFG, the library is initially unknown, and the input strings encode observations of the activities to recognize. Activity recognition is traditionally considered independent of the research done on automated planning, using handcrafted libraries of activities and specific algorithms [Ravi et al., 2005]. An exception is the work by Ram´ırez and Geffner [2009; 2010] where goal recognition is formulated and solved with planning. As far as we know our work is the first that tightly integrates the tasks of (1) grammar learning, (2) recognition and (3) production using a common planning model and an off-the-shelf classical planner.

Hierarchical Task Networks (HTNs) is a powerful formalism for representing libraries of plans [Nau et al., 2003]. HTNs are also defined at several levels such that the tasks at one level are decomposed into other tasks at lower levels with HTN decomposition methods sharing similarities with production rules in CFGs. There is previous work in generating HTNs [Hogg et al., 2008; Lotinac and Jonsson, 2016] and an interesting research direction is to extend our approach for computing HTNs from flat sequences of actions. This aim is related to Inductive Logic Programming (ILP) [Muggleton, 1999] that learns logic programs from examples. Unlike logic programs (or HTNs) the CFGs that we generate are propositional and do not include variables. Techniques for learning high level state features that include variables are promising for learning lifted grammars [Lotinac et al., 2016].

6 Conclusions

There is exhaustive previous work on learning CFGs given a corpus of correctly parsed input strings [Sakakibara, 1992; Langley and Stromsten, 2000] or using positive and negative examples [De la Higuera, 2010; Muggleton et al., 2014]. This work addresses generating CFGs using only a small set of positive examples (in some cases even one single string that belongs to the language). Furthermore we follow a compilation approach that benefits straightforwardly from research advances in classical planning and that is also suitable for production and recognition tasks with arbitrary CFGs.

Our compilation bounds the number of rules m, the length of these rules n, the size of the stack ℓ and the length of the input strings z. If these bounds are too small, the classical planner used to solve the output planning task will not be able to find a solution. Larger values for these bounds do not formally affect to our approach, but in practice, the performance of classical planners is sensitive to the size of the input. Interestingly our approach can also follow an incremental strategy where we generate the CFG for a given sub-language and then encode this sub-grammar as an auxiliary procedure for generating more challenging CFGs [Segovia-Aguas et al., 2016b].

The size of the compilation output also depends on the number of examples. Empirical results show that our approach is able to generate non-trivial CFGs from very small data sets. Another interesting extension would be to add negative input strings, which would require a mechanism for validating that a given CFG does not generate a given string, or to accept incomplete input strings that would require combining the generation and production mechanisms.

Acknowledgements

This work is partially supported by grant TIN2015-67959 and the Maria de Maeztu Units of Excellence Programme MDM2015-0502, MEC, Spain.