# What is the subset of CFGs called where each expansion must be the same?

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).

• What do you mean by "all rules must be the same"? wouldn't it make them redundant? Commented Oct 29, 2021 at 15:54
• @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. Commented Oct 29, 2021 at 16:05
• 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.. Commented Oct 29, 2021 at 16:53
• 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$. Commented Oct 29, 2021 at 17:09
• @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. Commented Oct 29, 2021 at 22:03

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.