Hi,
I want to know if its possible to write a regular expression for a context free language:

For example I have a language : L={a^n b ^m: n<= m +3}

I have written the following regular expression for it:

a*bbb(b)*

Is this possible? Somebody please guide me.

Zulfi.

 

Remember how I've been harping on you to always take a look at your solutions and ask if they make sense?

Can you not see any way to use your expression to generate a string that has more a's than b's (which would clearly not be in the language)?

Try to rewrite your language description into a form that leverages what you already know how to do (supposedly).

Assuming you know how to write a grammar for

L1 = {a^n b ^n: n ≥ 0}

Can you describe the language L2 such that

L = L1 · L2

 

Remember how I've been harping on you to always take a look at your solutions and ask if they make sense?

Can you not see any way to use your expression to generate a string that has more a's than b's (which would clearly not be in the language)?

Try to rewrite your language description into a form that leverages what you already know how to do (supposedly).

Assuming you know how to write a grammar for

L1 = {a^n b ^n: n ≥ 0}

Can you describe the language L2 such that

L = L1 · L2

Hi,
Good question, I would certainly try it, but in this situation its a digression because I am asking about regular expression. I don't want to change the concentration of my question. We should start another thread for that.
Zulfi.

 

If you want to right a regular expression for a context-free grammar, then the first thing that you have to do is establish that it is not just context-free, but that it is actually a regular language.