0
$\begingroup$

I was wondering about a kind of grammar where we can expand rules of the form A -> X|Y|... with A being a nonterminal and X and Y being strings of nonterminals or terminal symbols, but the expansions of X and Y (and all other rules under A) must all be the same. Is there a name for this? It feels like it is probably a subset of the class of context free grammars, in which X and Y could be different or could even contain A or be empty (which should both also not be allowed for this grammar).

$\endgroup$
6
  • 1
    $\begingroup$ What do you mean by "all rules must be the same"? wouldn't it make them redundant? $\endgroup$
    – nir shahar
    Commented Oct 29, 2021 at 15:54
  • $\begingroup$ @nirshahar in terms of the language it generates yes, but I need the data structure for efficient search in the language. Basically every non-terminal should expand to exactly one literal string. $\endgroup$
    – stimulate
    Commented Oct 29, 2021 at 16:05
  • $\begingroup$ Actually, maybe it is not a subset of context free grammars.. because I would also like to have multiple starting symbols, which is not allowed in CFGs.. $\endgroup$
    – stimulate
    Commented Oct 29, 2021 at 16:53
  • $\begingroup$ Multiple starting symbols is easy to achieve. Say, you want $S_1,\dots ,S_k$ as your starting nonterminals. Then, for every $1\le i\le k$ add a rule $S\rightarrow S_i$. $\endgroup$
    – nir shahar
    Commented Oct 29, 2021 at 17:09
  • $\begingroup$ @nirshahar yes I know, but this only works in CFGs where S can have different expanisions. But I want every nonterminal to have one single expansion, but then multiple different starting symbols with different expansions, but each of them with one definite literal expansion. These expansions may have different rules, for example A -> ab, B -> bc, C -> Ac | aB, so here are multiple rules to expand C but they all expand to the same literals. $\endgroup$
    – stimulate
    Commented Oct 29, 2021 at 22:03

1 Answer 1

2
$\begingroup$

Every such language is finite and regular. Basically, we can think of the grammar as working as follows: we first make a decision for each non-terminal about which way it will expand; then that determines a single word that is accepted in this way. If there are $n$ non-terminals, and each rule as at most $k$ alternatives, then there are at most $k^n$ different ways to make those decisions, so at most $k^n$ words accepted by the grammar. Thus the language is finite, and therefore regular. I'm not aware of any "name" for this variant of context-free grammars.

$\endgroup$
1
  • 1
    $\begingroup$ Ah yes makes sense.. I just have one large disjungtion over all starting symbols and they all expand to a single string, which is regular.. $\endgroup$
    – stimulate
    Commented Oct 29, 2021 at 22:09

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.