1
$\begingroup$

How does the language $L=\{a^nb^mc^nd^m \mid n \geq1, m\geq1\}$ abstract the problem of checking that the number of formal parameters in the declaration of a procedure agrees with the number of actual parameters in a use of the procedure?

I simply didn't get what each of the variables $a,b,c,d,n$ and $m$ will represent? Seems $1^{st}$ pair $(n,m)$ is for formal parameters and later for actual. But I didn't get why there are $a$ and $b$? Couldn't only single variable be ample?

Improve this question
$\endgroup$
2
  • $\begingroup$ It should be nice if you can clarify in the question its context is to show some programming languages are not context-free. Or isn't it? $\endgroup$
    – John L.
    Commented Dec 8, 2018 at 18:19
  • $\begingroup$ @Apass okay sure. $\endgroup$
    – Mr. Sigma.
    Commented Dec 8, 2018 at 23:03

1 Answer 1

Reset to default
2
$\begingroup$

The language

$$L=\{a^nb^mc^nd^m \mid n \geq1, m\geq1\}$$

abstracts agreement of parameter and argument count for the case where there are exactly two procedures, one with $n$ parameters, declared with $a^n$ and used with $c^n$, and the other one with $m$ parameters, declared with $b^m$ and used with $d^m$. Each procedure is called exactly once and the calls are interleaved with the declarations. The interleaving makes it impossible for a context-free grammar to specify agreement.

One might be tempted to generalize to more uses of each procedure:

$$L'=\{a^nb^m\omega \mid n \geq1, m\geq1, \omega \in \{c^n,d^m\}^*\}$$

or more procedures (I'm not going to try writing that one out), but it just serves to make everything more complicated to no purpose.

The simple example is easily proven to not be context free, and the simplification can be justified by observing that context-free languages are closed under substitution which is a very powerful and useful proof technique. (The fact that declarations and uses can be reduced to repetition of a simple symbol is also justified by substitution. A starting point for Algol-style languages might be to remove all the parameters/arguments from a declaration/call, leaving only the commas and parentheses. For S-expressions it's even simpler.)

So the abstraction provides a simple proof (as well as some intuitive basis) for why parameter/argument agreement cannot be incorporated into a context-free grammar.

Improve this answer
$\endgroup$
3
  • $\begingroup$ This makes sense. What does the word $a^2b^2c^2d^2$ mean in that situation? I mean, it looks like it becomes ambiguous which usage of the procedure corresponds to which declaration. Can we use another language to abstract that kind of agreement when there are two different procedures of $n$ parameters each of which is called once right after its declaration? $\endgroup$
    – John L.
    Commented Dec 8, 2018 at 17:49
  • $\begingroup$ @Apass.Jack: Nothing prevents $n$ and $m$ from being equal. The point is that the language contains strings with all values of $n$ and $m$. Procedure naming is dealt with by using $a$/$c$ for declaration/use of the first procedure and $b$/$d$ for the second one. In effect, in the simplified grammar the procedures are always named a and b (except when they are used, when they are called c and d, respectively). The point of the simplification is not to parse the original program text in any way. It's simply to demonstrate a non-context-free reduction from the original language. $\endgroup$
    – rici
    Commented Dec 8, 2018 at 17:59
  • 1
    $\begingroup$ Because of closure, that demonstrates that the original language was not context-free. That's the only point here. Nothing more. $\endgroup$
    – rici
    Commented Dec 8, 2018 at 17:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.