1
$\begingroup$

Word grammar (w-grammar) is a context free grammar in which all laws are of the following forms:

$A \rightarrow B, A \rightarrow \epsilon, A \rightarrow w_1B, A \rightarrow Bw_2$

$A, B \in N$ (nonterminal), $w_i \in \Sigma^\ast$

$ L_{w-grammar} $ - set of all languages that have a w-grammar

$ L_{CFG} $ - set of all languages that have a context free grammar

Is the following statement is true $ L_{CFG} \subseteq L_{w-grammar} $ ?

$\endgroup$
1
$\begingroup$

The class of languages accepted by this kind of grammar is known as linear languages (the definition on Wikipedia is slightly different, but equivalent). According to Wikipedia, the language of all balanced parentheses (generated by $S \to SS \mid (S) \mid \epsilon$) is context-free but not linear.

$\endgroup$

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.