10
$\begingroup$

From my reading it seems that most grammars are concerned with generating an infinite number of strings. What if you worked the other way around?

If given n strings of m length, it should be possible to make a grammar that will generate those strings, and just those strings.

Is there a known method for doing this? Ideally a technique name I can research. Alternatively, how would I go about doing a literature search to find such a method?

$\endgroup$
2
  • 5
    $\begingroup$ Trivial: Construct BNF table of the strings. $\endgroup$
    – Joshua
    Feb 18, 2016 at 17:10
  • $\begingroup$ Strings are finite by definition. And you can't get an infinite set be "given" unless you have some finite description of it. $\endgroup$
    – vonbrand
    Mar 9, 2016 at 22:44

5 Answers 5

Reset to default
12
$\begingroup$

This falls within the general topic of "grammar induction"; searching on that phrase will turn up tons of literature. See, e.g., Inducing a context free grammar, https://en.wikipedia.org/wiki/Grammar_induction, https://cstheory.stackexchange.com/q/27347/5038.

For regular languages (rather than context-free ones), see also Is regex golf NP-Complete?, Smallest DFA that accepts given strings and rejects other given strings, Are there improvements on Dana Angluin's algorithm for learning regular sets, and https://cstheory.stackexchange.com/q/1854/5038.

$\endgroup$
2
  • $\begingroup$ Inducing grammars for possibly infinite regular languages is hard and quite different from this problem. $\endgroup$
    – reinierpost
    Feb 18, 2016 at 14:52
  • $\begingroup$ I'm marking this question correct, because although it does not directly answer the question (which it turns out is trivially solvable as stated), it does provide me with the kind of terminology I need to do further research. $\endgroup$
    – Gustav Bertram
    Feb 19, 2016 at 8:48
9
$\begingroup$

If the number of strings is finite say set $S=\{s_1,s_2....s_m\}$ you can always come up with context free grammar that generates all those strings, let $A$ be a non terminal then the rule can be $A \to s_1|s_2|...s_n$. For a finite set of strings you can even come up with a finite state automata that accepts only those strings. So the case of finite set of strings is really trivial.

$\endgroup$
1
  • $\begingroup$ I think I need to review my parsing textbook. In retrospect this answer seems obvious. Thank you! $\endgroup$
    – Gustav Bertram
    Feb 18, 2016 at 11:41
3
$\begingroup$

What you are asking is akin to a search index. Indeed Finite State Transducers can be created and used to recognize text fed to them. For exameple, Lucene uses this algorithm: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.3698

For a practical use, check out this blog post by Andrew Gallant: Index 1,600,000,000 Keys with Automata and Rust

In the post he describes a method to construct a FSA given a corpus of text such that it recognizes all the words. The end result is to construct an approximately minimal FST from pre-sorted keys in linear time and in constant memory.

FSA sharing prefixes and suffixes

The implementation is available in his fst library: https://github.com/BurntSushi/fst

$\endgroup$
3
$\begingroup$

There are lots of ways, so you need to impose additional criteria on the quality of the results. Examples:

  1. List: For each string $w$ in the language, have a rule $S \rightarrow w$. Let $S$ be the starting nonterminal. Done.
  2. Prefix tree: For each prefix $w$ of a string in the language, have the nonterminal $X_w$. For each string $w_1xw_2$ in the language, where $x$ is a symbol, have the rule $X_{w_1} \rightarrow xX_{w_2}$. For each string $w$ in the language, have rule $X_w \rightarrow \epsilon$. Let $X_\epsilon$ be the starting nonterminal. Done.
  3. Suffix tree: the same, reversed.
  4. Applying an algorithm guaranteed to produce a grammar of minimal size, e.g. with the minimal number of rules. I don't know how hard this is.
$\endgroup$
2
  • $\begingroup$ Yes, after the first answer it was obvious I should have imposed additional criteria, but it felt unfair to change the question after the first answer. $\endgroup$
    – Gustav Bertram
    Feb 19, 2016 at 8:47
  • $\begingroup$ Still, I'd love to know the time complexity of finding a minimal grammar for a given finite set of strings ... let's say, in the total length of the strings, or in the total length of the result. $\endgroup$
    – reinierpost
    Feb 19, 2016 at 8:49
1
$\begingroup$

An answer to the question posed by reinierpost which also answers the original question:

We construct the dictionary automaton as follows:

  1. construct an automaton that reads and accepts exactly the first string.
  2. for the next string, start reading it with the automaton until for some letter there is no transition. start a new branch for the rest of the string. repeat until all strings are processed

The maximal size of the automaton is the total length of the input strings. Assuming that you can simulate transitions and create new ones in constant time, also the runtime is the total length of the input strings. No best or worst cases.

This automaton is minimal. since in the regular case automata and grammars correspond almost one to one, the same is true for the grammar, Of course, it is impossible to construct something of size n in less than n time.

$\endgroup$
5
  • $\begingroup$ Thanks. As far as answering this question: I don't see what this contributes over reinierpost. Also, we don't want answers that respond to or comment on another answer: this is not a discussion forum. The way to do that would be to post a new question and then answer it yourself. I realize that might not be obvious. [That said, I don't see how your answer answers the problem reinierpost was curious about. The problem at the end of reinierpost's answer was to find a grammar with the minimum number of rules. Your answer shows how to build a DFA with minimal number of states. (continued) $\endgroup$
    – D.W. ♦
    Mar 9, 2016 at 16:46
  • 1
    $\begingroup$ Of course we can convert that DFA to a regular grammar, but what makes you think it will be minimal in terms of the number of rules in the grammar? It seems like that needs proof.] $\endgroup$
    – D.W. ♦
    Mar 9, 2016 at 16:46
  • $\begingroup$ What my answer contributes is the runtime, I think. You are right, several things I say would need some proof. But the correspondence between Finite Automata transitions and Regular Grammar rules is very clear for me (if the latter can only generate one terminal per rule as in most definitions); then any grammar smaller than mine would give an automaton smaller than the minimal one. So I think the grammar from the minimal automaton (I do not prove that mine is minimal) will be minimal, too. -- I will keep your advice concerning answers in mind, thanks $\endgroup$
    – Peter Leupold
    Mar 9, 2016 at 17:46
  • $\begingroup$ The notion of minimality for DFA's is with respect to the number of states. Does this imply minimality with respect to number of transitions in the DFA, or minimality of the number of rules in the resulting grammar? I think we have to keep track of what your metric is, as otherwise I'm worried we'll be comparing apples to oranges. $\endgroup$
    – D.W. ♦
    Mar 9, 2016 at 17:50
  • $\begingroup$ Correct, The grammar will be minimal in termson non-terminals. For rules, this is not clear. $\endgroup$
    – Peter Leupold
    Mar 9, 2016 at 18:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.