Context free languages that has only one non-terminal is a proper subset of context free languages and they does not contains regular set. Since, CFL is more powerful than FSM and contains regular set, there must be some languages that requires more than one non-terminal. How can I show or proof this formally?

  • $\begingroup$ Consider the language $L=\{a^mb^{m+n}a^n\ |\ m,n\in\mathbb{N}\}$. Suppose you want to construct a single-nonterminal CFG $G$ for $L$; see if you can find restrictions of allowable rules (from the fact that $G$ must not generate any words outside $L$). $\endgroup$ Dec 29 '15 at 13:40
  • 3
    $\begingroup$ Your question is answered on math.se. See math.stackexchange.com/questions/241991/… and math.stackexchange.com/questions/468520/…. $\endgroup$ Dec 29 '15 at 13:46
  • $\begingroup$ Your post exhibits confusion with terminology. Make sure you understand the difference between languages, grammars, and classes of either. For instance, "CFL is more powerful than FSM" is a nonsensical statement; you attempt to compare languages and automata. $\endgroup$
    – Raphael
    Dec 29 '15 at 14:26
  • $\begingroup$ It's not clear to me what the question is. You already state that "single-non-terminal CFL" is a proper subset of CFL. Do you want a witness for that? If so, what do you need regular languages (and their inclusion in CFL) for? $\endgroup$
    – Raphael
    Dec 29 '15 at 14:28
  • 3
    $\begingroup$ Note there are two ways to interpret your restriction. (1) The grammar has only a single nonterminal, which must be the axiom $S$, but may contain productions involving serveral nonterminals (at the RHS) like $S\to SS$. (2) The grammar has possibly several nonterminals, but each sentential form (derived string) contains at most one nonterminal. Typical productions are like $X\to aYb$. Such grammars and their languages are called "linear". $\endgroup$ Dec 29 '15 at 15:43

Consider the language $L=\{a^mb^{m+n}a^n\ |\ m,n\ge 1\}$. From the assumption that there is a single-nonterminal CFG $G$ for $L$, we can derive constraints which eventually lead to a contradiction.

$G$ is given by the (singleton) set $\{S\}$ of nonterminals, set $\{a,b\}$ of terminals, and some number of rules $S\to w_i$ for $w_i\in\{a,b,S\}^*$. There are some obvious conditions:

  1. There must be some $i$ such that $w_i$ contains $a$.
  2. There must be some $j$ such that $w_j$ contains $b$.
  3. There must be some $k$ with $w_k\in\{a,b\}^*$.

Note that some of $i,j,k$ might coincide, but this does not matter. Now suppose that there is some $l$ such that $w_l$ contains more than one $S$, i.e. $w_l=xSySz$ for some $x,y,z$. Then $S\to xSySz\to xxSySzySz\to\dots\to xxw_jyw_izyw_jz$ which contains a $b\dots a\dots b$ subsequence, i.e. we get a word outside $L$ (once any additional $S$ which might occur inside $x,y,z$ are replaced with $w_k$).

So the rules in $G$ really can only be of the forms $S\to u_iSv_i$ or $S\to w_i$ with $u_i,v_i,w_i\in\{a,b\}^*$. Since we can only use one of the latter form when building a word, and we may need arbitrarily many $b$, we get

  1. For some $i$, either $u_i$ or $v_i$ contains a $b$. We will assume wlog that it is $v_i$; the $u_i$ case is symmetric.

Suppose that there is also a $j$ such that $v_j$ contains $a$; then $S\to u_iSv_i\to u_ju_iSv_iv_j\to u_iu_ju_iSv_iv_jv_i$, which again contains a $b\dots a\dots b$ subsequence and takes us out of $L$. Therefore

  1. $v_i\in b^*$ for all $i$.

But the words in $L$ all end with an $a$, so

  1. $v_i=\epsilon$ for all $i$.

But then $G$ is a regular grammar and cannot generate a non-regular language like $L$.

  • 1
    $\begingroup$ Bah humbug, should have checked comments first. $\endgroup$ Dec 29 '15 at 15:22

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.