This grammar describes a language that may fall outside the Chomsky Hierarchy (CH):

\begin{array}{l} S \to abAbba \\ A \to abA \mid bbaB \\ B \to aab \\ \lambda \to Aab \mid aB \\ \end{array}

Going down the list, it's not context-free, it's not regular, etc. Getting all the way to RE languages, the production starting with $\lambda$ seems outside any possible language within the CH. Does this grammar not fall within the CH?

  • $\begingroup$ Maybe I'm being thick, but what's $\lambda$? $\endgroup$ – fgp Dec 8 '13 at 18:15
  • $\begingroup$ Ah, OK, seems that $\lambda$ is simply the zero-length word. So your last production allows the right-hand side to be inserted anywhere, right? $\endgroup$ – fgp Dec 8 '13 at 18:19
  • $\begingroup$ Yes the $\lambda$ would be the empty string, and so that's a production starting from nothing to something. $\endgroup$ – stackuser Dec 8 '13 at 18:23

The last rule of your grammar does not satisfy the requirements of a formal grammar (every rule in formal grammar must have at least one non-terminal symbol on the left-hand side), so it clearly cannot belong to any hierarchy of formal grammars.

That being said, the language produced by your grammar (under the intuitive semantics) falls into the class of recursively enumerable languages. At a glance, it should be sufficient to add a non-terminal symbol $L$, along with rules $L\rightarrow \lambda\ | LL$ and add $L$ before, after and between each pair of characters on the right-hand sides of the rules (e.g. the third rule would become $L\rightarrow LaLaLbL$).

As coffeemath correctly observed, the resulting grammar will be context-free, so the language itself is context-free, instead of being just recursively enumerable.

  • 3
    $\begingroup$ With the extra symbol $L$ as suggested, does this now become context-free, since after the suggestion all rules have no context combinations to the left of the productions? $\endgroup$ – coffeemath Dec 8 '13 at 19:17
  • 1
    $\begingroup$ @coffeemath: Certainly looks like it to me. $\endgroup$ – Brian M. Scott Dec 8 '13 at 19:55

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.