2
$\begingroup$

Let $G=(V, \Sigma, R, S)$ be a (non regular) probabilistic context-free grammar, and $u_1, \ldots, u_n$ a set of $n$ strings generated by $G$.

For finite $n$, it is always possible to find a regular grammar $\hat G=(\hat V, \Sigma, \hat R, S)$ which generates the strings $u_1, \ldots, u_n$.

Intuitively, as $n$ goes to infinity, we expect $\hat G$ to get larger: my guess is that the cardinal of $\hat R$ (and maybe also the cardinal of $\hat V$?) would need to go to infinity.

Are there results which formalize this, e.g. by giving a lower bound on these cardinals as a function of $n$?

Improve this question
$\endgroup$
4
  • $\begingroup$ Are you referring to strictly regular grammars or are extended ones also allowed? $\endgroup$
    – dkaeae
    Commented Dec 20, 2018 at 13:08
  • $\begingroup$ @dkaeae I am mostly interested in strictly regular grammars, but would also welcome answers related to extended ones. $\endgroup$
    – Robin Ryder
    Commented Dec 20, 2018 at 13:38
  • 1
    $\begingroup$ If we replace probabilistic context-free grammar by (usual) context-free grammar in the question, does it make any difference? If it does, please clarify. $\endgroup$
    – John L.
    Commented Dec 21, 2018 at 8:01
  • $\begingroup$ @Apass.Jack I would be equally happy with an answer about usual CFGs. Using PCFGs means that it might be possible to get a probabilistic statement, e.g. about the expected value of the cardinal of $\hat R$. $\endgroup$
    – Robin Ryder
    Commented Dec 21, 2018 at 9:24

1 Answer 1

Reset to default
1
$\begingroup$

The question, if understood in the simplest naive way, might be uninteresting.

Here is a simple example. Let $G$ be the regular language $\{a^n\mid n\ge0\}$ over the alphabet $\{a\}$. Consider the strings $\epsilon, a, a^2, \cdots, a^n$ in $G$. What are the regular languages that contains those strings?

  • The minimal such language, i.e., which contains no other strings, will need $n+1$ generation rules $S\to a^i$ for $0\le i\le n$.
  • The language with the least generation rules is $G$ itself, which has two generations rules $S\to \epsilon$ and $S\to aS$.

However, once we start to twiddle with the ways how to approximate context-free grammar by regular grammar, there are tons of research.

Here is a related question that links to many related stuff, Is there a known method for constructing a grammar given a finite set of finite strings?.

This paper considers approximating CFG from above by a regular grammar.

You can browse the google search result for approximate context-free grammar by regular grammar or the google scholar.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Practical Experiments with Regular Approximation of Context-Free Languages seems interesting. $\endgroup$
    – John L.
    Commented Dec 26, 2018 at 10:55
  • $\begingroup$ Thank you for the links! However, I don't understand your example, since your $G$ is regular, so of course $\hat G=G$ works. $\endgroup$
    – Robin Ryder
    Commented Dec 28, 2018 at 8:11
  • $\begingroup$ That is exactly the point. I am saying there are ways to interpret the requirement of $\hat G$ that makes the solution uninteresting. $\endgroup$
    – John L.
    Commented Dec 29, 2018 at 9:17
  • $\begingroup$ I tried to phrase the question in a way that would specifically avoid this case, with $G$ a non-regular (P)CFG. $\endgroup$
    – Robin Ryder
    Commented Dec 29, 2018 at 10:39
  • $\begingroup$ I noticed your attempt to emphasize non-regular-ness. However, you can just attach another piece to $G$, such as $\{a^nb^n\mid n\ge0\}$ to make it non-regular. $\endgroup$
    – John L.
    Commented Dec 29, 2018 at 12:24

Your Answer

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

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