PDA

View Full Version : Context-Free Grammar

jacobM
April 5th, 2009, 08:14 PM
K, these are quite easy for me now to get a CFG for a CFL.
But ive run into a new problem with some notation. I cannot put my finger on exactly what this notation means.

Here it is.

L3, L*, L complement for the language

L = {a^n.b^n : n ≥ 1} on = {a, b}.

The CFG for this is of course quite simple. I just can'f figure out exactly what the notations mean. Does this have anything to do with closure properties?
Any help is greatly appreciated.

Arndt
April 5th, 2009, 09:33 PM
K, these are quite easy for me now to get a CFG for a CFL.
But ive run into a new problem with some notation. I cannot put my finger on exactly what this notation means.

Here it is.

L3, L*, L complement for the language

L = {a^n.b^n : n ≥ 1} on = {a, b}.

The CFG for this is of course quite simple. I just can'f figure out exactly what the notations mean. Does this have anything to do with closure properties?
Any help is greatly appreciated.

Neither can I, but where did you get it? (CFL means context-free language, I suppose.)

* is commonly used for closure, but I don't know what the 3 stands for. Maybe S1S2S3, where S1, S2 and S3 all belong to L?

(I don't know if this is programming, but why not.)

jacobM
April 6th, 2009, 05:52 AM
I think
L3 is (a^n b^n)(a^n b^n)(a^n b^n)
L* is (a^n b^n) and the empty set
L complement is everything other than (a^n b^n) so kinda would be (a^n b^m)

Just in case anyone was wondering and to kinda answer this post/myself :) lol.

CptPicard
April 6th, 2009, 10:04 AM
I guess L3 means what you think it means (are you talking of L^3, with 3 in the exponent?), but I can't see how complement would look like that. It's more like

{a,b}* \ {a^nb^n : n ≥ 1}

And the closure

{a^n.b^n : n ≥ 1}* =

{<empty>, ab, aabb, abaabb, aabbab, aaabbb, abaaabbb, aaabbbab,
abaabbaaabbb, abaaabbbaabb, ... <all concatenated combinations of what you can generate>}

I can't really think of better set-representations for the two...