Context free grammar and regular expressions

92 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.