Interpreting a Language

Question

I'm having trouble understanding some language notation, primarily what rules I can take away from it. The language is as follows:

$\qquad L = \{a^n b^m b^p c^p b^{n-m} \mid n > 0, m < n, p > 2\}$

My goal is to create a context free grammar from this, but I can't get my ahead around the rules in place here. In plain English, it's clear that any string for this language must have a positive number of a's in it, but what is going on with the multiple b's? Do I take this as the string must be in some form like so:

$\qquad aaa-b-bbb-ccc-bb$ (n=3, m=1, p=3)

where the bunches of b's are just distinct sequences? Or is there something else I should be doing in order to satisfy this?

Answer 1

First of all, note that your quest for "rules in place" is probably doomed. This looks pretty much like an exercise problem you would pose in class; there is not necessarily an intuitive rule or semantics. It's just a playground for developing your skills. Therefore, it may be more helpful to strap on theory glasses and just look at the formal object given to you.

Now, for your problem. In order to get to a context-free grammar, it can be useful to identify "phases" a grammar can work through. A good first step is to identify which parts of the word are "connected" by the restrictions in place and which are independent of each other. If you find intersecting dependency arcs, you either have a non-context-free language (which you can check) or you need to represent your language differently (sometimes restrictions are redundant or seem to imply dependencies that are not really there¹).

Here, note that your words have the form

$\qquad a^n b^m \dots b^{n-m}$.

Why can I remove a part for an intuitive look? Because I cut away $b^p c^p$ which can clearly by generated by a standard grammar and independently of the rest. Now, the above is just

$\qquad a^n b^n$

if you remember to insert $b^p c^p$ at some point in $b^n$.

Try to come up with a grammar along these lines. Take care about corner cases and the exact restrictions on $m,n,p$! And, of course, prove correctness.

Another strategy that can sometimes work better is to build a PDA and convert it into a(n ugly) grammar by the standard construction.

---

1. A simple example: $a^nb^nc^n$ is not context-free, so $a^na^na^n$ is not. Right? Wrong: $a^na^na^n = a^{3n}$ is clearly regular.

Answer 2

On your question about what the language $L$ means:

Yes, that's right, except that the dividing lines between the blocks are not provided to you. Thus, one example string in $L$ would be aaabbbbcccbb ($n=3,m=1,p=3$) (not aaa-b-bbb-ccc-bb; you're not given the dividing line). Another example string would be aaabbbbbbccccb ($n=3,m=2,p=4$).

If it helps understand what the notation means, here is another equivalent way to express the language $L$:

$$L = \{a^n b^{m+p} c^p b^{n-m} | n>0, m<n, p>2\}$$

though this equivalent formulation might not make your life of finding a context-free grammar any easier (actually, it'll probably make things harder).

Finding the context-free grammar is up to you; I'm just trying to help you understand what the language $L$ is.