views:

94

answers:

2

I have a question from a test in a Programming Languages class that is confusing me.

Give a context-free grammar to generate the following language

L = { aibjck | 0 <= i <= j <= i + k }

I am completely unfamiliar with this notation. I cant seem to find anything in the book or my notes about it, and I have no idea how to query google for the answer.

If you recognize it, what is it called and what does it mean?

+2  A: 

a^i just means a repeated i times. So a^2 = aa, b^10 = bbbbbbbbbb, etc.

Claudiu
sooooo that should mean"", "a", "c", "ab", "bc", "abc", "abbc"are all strings in the language L.
Nathan
A: 

Often,

  • {} means "the set of"
  • | means "such that"

I have no idea what a, b, c are. i and j are non-negative numbers, being greater than or equal to zero. Conventionally, those letters are reserved for integers. The fact that

i <= i + k

means that k is also non-negative.

If a, b, and c are reals, then it seems to me that L is just the set of real numbers. However, it seems like a very contrived and elaborate way of specifying it. That would be something like Dr. Evil's plot to kill Austin Powers.

So you have "the set of a to the power i times b to the power j time c to the power j such that i, j and k are positive, and j is greater than or equal to i ..." and so on.

Ewan Todd
Almost. a, b and c are terminal symbols in the language L. L is basically being defined as all strings of 'a' followed by 'b' followed by 'c', such that there are zero or more of 'a', the same or more of 'b', and the number of 'a' and 'c' together is greater or equal to the number of 'b'.
Barry Kelly
Interesting, Barry. What keyword do I look for to learn about it?
Ewan Todd
Ah, "Context -free Grammar". http://en.wikipedia.org/wiki/Context-free_grammar
Ewan Todd