I find some references say that

all the features of programming language fall within what can be captured by context-sensitive grammars. In fact, no programming language known to humankind anything that cann't.


Actually, most of programming language is context-free language.

Q1: Are the claims correct? I did not find some bibiographies about a precise description or even a proof.

Let $\Gamma$ be the alphabet of the instructions of a programming language. Given a specific procedure $P$, all of its control flows belong to $L_{P}$. $L_{P}$ describes how does it control its data.

At the same time, for every $x \in \Sigma^*$, $P$ computes it and gives an output $P(x)$. Assume that $P$ is used to slove a decision problem, i.e., $P(x) \in \{ 0,1 \}$. There is a language $L'_{P} = \{ x \in \Sigma* \mid P(x) = 1 \}$. If we regard $P$ as a machine, $L'_P$ describes the computational power of $P$.

It is obvious that $L_P$ and $L'_{P}$ are totally different.

Q2: What is the relation between $L_P$ and $L'_{P}$? Is there a conclusion such that $$L_P \in CFL \Leftrightarrow L'_P \in CFL$$ or $$L_P \in CSL \Leftrightarrow L'_P \in CSL$$


There is no interesting relation between a programming language (the set of words which are syntactically valid programs) and the set of words that are accepted by a program written in said programming language.

Note that it is possible to design a Turing powerful programming language which, as a formal language, is the set $1^* = \{\epsilon,1,11,111,\ldots\}$.

Still, program $1^n$ will accept a language $L_n$ which is completely unrelated to $1^*$. Indeed, by Turing completeness, for any r.e. language $A$ there is some $n$ such that $A=L_n$.

The crucial aspect to consider here is the semantics of the programming language, the way we map each program $1^n$ to its behavior, and ultimately to the set of accepted words $L_n$. Even if $1^*$ is a very simple language, the semantics can still make it Turing powerful, so that $L_n$ can be any r.e. language.


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.