5
$\begingroup$

The classic example of a context-free grammar is $a^nb^n$. That is, $n$ occurrences of $a$ followed by an equal number of occurrences of $b$.

Do such forms occur in the real world? Can you provide an example of a real-world case where there must be $n$ occurrences of something followed an equal number of occurrences of something else?

Let me give an example: if I run an on-line store, then for each purchase made to my store, there must be a corresponding delivery of the purchased item. That might be modeled as $n$ purchases followed by $n$ deliveries:

purchase purchase purchase delivery delivery delivery

However, that is not a good data model since each delivery should legitimately be paired to a purchase:

purchase delivery purchase delivery purchase delivery

So I am left wondering if there are any real-world examples where data would be (legitimately) modeled as a sequence of $n$ items of one type followed by $n$ items of another type. Can you provide a real-world example please?

Hendrik Jan provided this good example (see it in the comments below): This weekend I visited my mother. Three flights up, and three flights down when I left.

Neat example! Can you think of others?

A colleague just informed me of another example. In the KML specification it says that a <Track> element must contain N <when> elements followed by N <gx:Coord> elements:

https://developers.google.com/kml/documentation/kmlreference#gxtrack

Another excellent example. What are other examples?

Another colleague sent me an article about columnar databases. It is often more efficient to store data in columns rather than rows. For example, we may have a column of person's ages followed by a column of person's heights. Or, a list of N integers (ages) followed by a list of N decimals (heights). This enables efficient calculation of sums or averages. Here's the article:

http://www.postgresql.org/message-id/52C59858.9090500@garret.ru

More examples please! I would like for us to create a nice collection of compelling examples.

|cite|improve this question
$\endgroup$
  • $\begingroup$ Note that languages and grammars are not the same. And you can use LaTeX here. Now, was for your question, what scope do you assign "real world"? Are examples from computing (arguably many-made/imaginary) fine? $\endgroup$ – Raphael♦ Jan 3 '14 at 14:02
  • $\begingroup$ Hello Raphael, I am seeking real-world examples where the best way to model data is as n occurrences of something followed an equal number of occurrences of something else. For example, for every purchase there must be a corresponding delivery. But that's not good because the best way to model that is with an arbitrary number of purchase-delivery pairs, not as n purchases followed by n deliveries. So I am wondering if there exist any examples of where it is appropriate to have n items of something followed by n items of something else? Is an bn simply artificial? $\endgroup$ – Roger Costello Jan 3 '14 at 14:08
  • 2
    $\begingroup$ By the way, your "purchase-delivery pairs" correspond to the Dyck language which (somewhat) characterises the class of context-free languages. Now this one is everywhere. $a^n b^n$ is just a special case. $\endgroup$ – Raphael♦ Jan 3 '14 at 14:16
  • 3
    $\begingroup$ Real world example. This weekend I visited my mother. Three flights up, and three flights down when I left. $\endgroup$ – Hendrik Jan Jan 3 '14 at 16:40
  • 2
    $\begingroup$ Please don't include answers in your question; that's what answer posts are for. Also, you should probably avoid making this a list question since there is a general dislike towards these. Please note also this and this discussion $\endgroup$ – Raphael♦ Jan 6 '14 at 10:17
12
$\begingroup$

The classic consequence of $a^nb^n$ being context-free rather than regular is on opening and closing brackets. $a^nb^n$ represents the simplest possible case of this: no interleaving of opens and closes and no intervening characters. Regular expressions can't even deal with this most basic case.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ What? Yes they can. $\endgroup$ – Lex R Jan 25 '14 at 18:17
  • 2
    $\begingroup$ @LexiR Your regular expression matches the string "((()))" and no other. Obviously, such a regular expression exists for any single string. However, you can't write a regular expression that matches exactly all strings formed by some number of ('s followed by the same number of )'s, and matching no other strings. Note also that programming languages such as Perl often implement extensions to regular expressions; in computer science, "regular expression" has a specific definition. $\endgroup$ – David Richerby Jan 25 '14 at 19:20
  • $\begingroup$ @LexiR your Regex generates finite set that is still a regular, you could argue for $a^nb^*a^n$ and it is possible to write Regex in Perl and Python But it don't mean that $a^nb^*a^n$ is a regular (it is a liner CFG).The point is "class of language defined by Regex" ⊇ 'reglar languages'. Regex in programming is not exact same as Regular expression in formal languages. $\endgroup$ – Grijesh Chauhan Apr 10 '14 at 10:13
1
$\begingroup$

The famous $a^nb^n$ example actually occurs very often: in a way, you can think of this language as a comparison of two natural numbers. For example, any piece of code that compares two inputs is essentially solving $a^nb^n$.

Comparison occurs naturally as a condition (e.g. in an "if" statement, or a loop-termination condition). Thus, it is indeed a real-life problem.

However, you can also argue to the converse - in "real-life", everything is finite, so this language doesn't really occur. Still, this is an argument against every infinite language.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ Natural numbers are not usually encoded in unary. $\endgroup$ – Yuval Filmus Jan 3 '14 at 14:12
  • $\begingroup$ @YuvalFilmus - numbers per-se aren't encoded in unary, true, but sizes of data structures are essentially given in unary encoding, so this is still relevant. But indeed, perhaps one should also consider the language $\{ww:w\in \Sigma^*\}$ as a "natural" example, to include this. $\endgroup$ – Shaull Jan 3 '14 at 15:09

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.