Take the 2-minute tour ×

I really can't understand how we can simulate the output of a Turing machine (which accepts a recursively enumerable language) if we mostly code in context-free languages.

share|improve this question

closed as off topic by Barry Kaye, Chris Morgan, digEmAll, Wooble, Joe May 15 '12 at 13:16


2 Answers 2

up vote 7 down vote accepted

You are confusing the specification of a program with its output.

For example, a Turing machine that can accept a recursively enumerable language is still specified by a finite transition function or "rule table". The rule table itself can be expressed in a regular language.

Then again, only the basic syntax of a modern programming language is completely defined by a context free grammar. A valid program has to fulfill many conditions that are not captured by a grammar: identifiers have to be declared before they are used, a function can be defined only once, the program has to pass the typechecker, and so on.

share|improve this answer

"Mostly context-free" makes no sense in the same way that "slightly pregnant" makes no sense. The property is either there, or it isn't, and for any programming language I've ever used, it isn't.

But that's not the reason you can write arbitrary algorithms in them. The source code syntax of a language may or may not be describable by a particular grammar, but what matters is the input/output behaviour. For instance, a program that prints strings of the form A^iB^iC^i can be written in Pascal even though these strings do not form a context-free language. But the reason that this is possible is not that Pascal syntax is stronger than context-free (although that is true), it is the semantics of the constructs in Pascal (ultimately, the concept of the von Neumann machine on which the program will run).

share|improve this answer
"Mostly" as in most programming languages are context free. Some are not. –  Gabi May 15 '12 at 12:41
Oh, right. Sorry for mis-parsing that. –  Kilian Foth May 15 '12 at 12:43
