Consider a grammar $G = (V, \Sigma, R, S)$ where $V = \{S\}$, $\Sigma =\{A, B\}$ and $R$ has two production rules, namely $S \to S^+ AS $ and $S \to B$.

Is $G$ context-free? The $^+$ symbol is Kleene plus. The definition of a context-free grammar does not allow for regular expressions like $S^+AS$ on the right hand side, since it stands for infinitely many rules $S \to SAS$, $S \to SSAS$, $S \to SSSAS$, etc. Context free grammar only allows finitely many rules.

My motivation for asking stems from linguistics, where for grammatical categories like $NP$ and $VP$, a common phrase structure rule is $VP \to VP^+ \text{ CONJ } VP$. The author of the book I'm reading wrote this rule within context free grammar.


I think you can get around the finitely many rules problem by adding another symbol, $T$. Now you have $V = \{S,T\}$, and you can let $R$ have the production rules $S \to TAS, S \to B, T \to TS, T\to S$. Here $T$ is essentially a placeholder for "$S^+$", and it's easy to see that this yields the same language.

My take is that this means that even though the grammar you present is not context-free if you're being precise, it still describes a context-free language.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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