Context Free Grammar

[txrandom]

I have a problem where I can only figure it out by using CFG rules like so:

ij => iijjj
ij => iijjk
etc

Are you allowed to have two nonterminals on the LHS? For this particular problem, I don't see how to keep multiples sets of things in order.

 

[Krazy4Real]

/head asplodes

 

[AstroManLuca]

http://1.bp.blogspot.com/_xnSY...+fuck+am+I+reading.png

 

[fulltilt39]

Originally posted by: Krazy4Real
/head ass-plodes

Fixed.

 

[GodlessAstronomer]

I don't understand the question. Which are terminal/non-terminal? In my classes we used capital letters for non-terminals and small letters for terminals, eg.
As -> sAss

Edit - I didn't mean that to be a joke, I didn't even think about using A and s

 

[txrandom]

Originally posted by: GodlessAstronomer
I don't understand the question. Which are terminal/non-terminal? In my classes we used capital letters for non-terminals and small letters for terminals, eg.
As -> sAss

Oops,

they are both non-terminals, so it should be :

IJ => IIJJJ
IK => IIJJK

 

[GodlessAstronomer]

Originally posted by: txrandom

Originally posted by: GodlessAstronomer
I don't understand the question. Which are terminal/non-terminal? In my classes we used capital letters for non-terminals and small letters for terminals, eg.
As -> sAss

Oops,

they are both non-terminals, so it should be :

IJ => IIJJJ
IK => IIJJK

In that case the answer seems to be ambiguous, I'm not sure how you'd answer the question. If you wanted to simplify the rule set you could have ambiguous results, like
I -> IIJ
J -> JJ

or

I -> II
J -> JJJ

It's been a few months since I've done these things, maybe my thinking is all wrong, but I don't think the problem is solvable unambiguously. Have you posted all of the CFG rules?

Edit - to answer the question in the OP, I believe you are allowed to have multiple non-terminals on the LHS as long as the rule set can be simplified such that each rule has a single non-terminal on the LHS.

 

[txrandom]

Originally posted by: GodlessAstronomer

Originally posted by: txrandom

Originally posted by: GodlessAstronomer
I don't understand the question. Which are terminal/non-terminal? In my classes we used capital letters for non-terminals and small letters for terminals, eg.
As -> sAss

Oops,

they are both non-terminals, so it should be :

IJ => IIJJJ
IK => IIJJK

In that case the answer seems to be ambiguous, I'm not sure how you'd answer the question. If you wanted to simplify the rule set you could have ambiguous results, like
I -> IIJ
J -> JJ

or

I -> II
J -> JJJ

It's been a few months since I've done these things, maybe my thinking is all wrong, but I don't think the problem is solvable unambiguously. Have you posted all of the CFG rules?

Edit - to answer the question in the OP, I believe you are allowed to have multiple non-terminals on the LHS as long as the rule set can be simplified such that each rule has a single non-terminal on the LHS.

S -> IJK | e
I -> ab
J -> a
K-> b
IJ -> IIJJJ
IK -> IIJJK
JK -> KK | JJ

I'm trying to model the language (ab)^i a^j b^k where 2i = j + k. I'm mainly having trouble with figure out how to make sure the a^j and b^k stay in order (a's followed by b's).

 

[AstroManLuca]

Seriously, what the fuck are you guys talking about? Is this some sort of programming thing that I will never in a million years understand? Is this entire thread some joke that I'm not getting?

 

[txrandom]

Originally posted by: AstroManLuca
Seriously, what the fuck are you guys talking about? Is this some sort of programming thing that I will never in a million years understand? Is this entire thread some joke that I'm not getting?

Formal Language
CFG

 

[OCGuy]

My mommy says im special and gave me a gold star.

 

[AstroManLuca]

Originally posted by: txrandom

Originally posted by: AstroManLuca
Seriously, what the fuck are you guys talking about? Is this some sort of programming thing that I will never in a million years understand? Is this entire thread some joke that I'm not getting?

Formal Language
CFG

Well maybe this should be in programming or something then.

 

[txrandom]

Originally posted by: AstroManLuca

Originally posted by: txrandom

Originally posted by: AstroManLuca
Seriously, what the fuck are you guys talking about? Is this some sort of programming thing that I will never in a million years understand? Is this entire thread some joke that I'm not getting?

Formal Language
CFG

Well maybe this should be in programming or something then.

Nah, only a few programmers even touch this stuff. This stuff was around long before computers and programming.

 

[newnameman]

Originally posted by: txrandom

Originally posted by: GodlessAstronomer

Originally posted by: txrandom

Originally posted by: GodlessAstronomer
I don't understand the question. Which are terminal/non-terminal? In my classes we used capital letters for non-terminals and small letters for terminals, eg.
As -> sAss

Oops,

they are both non-terminals, so it should be :

IJ => IIJJJ
IK => IIJJK

In that case the answer seems to be ambiguous, I'm not sure how you'd answer the question. If you wanted to simplify the rule set you could have ambiguous results, like
I -> IIJ
J -> JJ

or

I -> II
J -> JJJ

It's been a few months since I've done these things, maybe my thinking is all wrong, but I don't think the problem is solvable unambiguously. Have you posted all of the CFG rules?

Edit - to answer the question in the OP, I believe you are allowed to have multiple non-terminals on the LHS as long as the rule set can be simplified such that each rule has a single non-terminal on the LHS.

S -> IJK | e
I -> ab
J -> a
K-> b
IJ -> IIJJJ
IK -> IIJJK
JK -> KK | JJ

I'm trying to model the language (ab)^i a^j b^k where 2i = j + k. I'm mainly having trouble with figure out how to make sure the a^j and b^k stay in order (a's followed by b's).

I don't think I've ever seen a CFG with more than one non-terminal on the LHS, but you shouldn't need to do that anyways. I think something like this should work:

S -> S'b | R | e
S' -> abSb | R' e
R -> R'a | e
R' -> abRa | e

 

[GodlessAstronomer]

Originally posted by: AstroManLuca
Seriously, what the fuck are you guys talking about? Is this some sort of programming thing that I will never in a million years understand? Is this entire thread some joke that I'm not getting?

:laugh: It's not really programming, it's esoteric computer science stuff. It's the kind of thing you learn, pass an exam then never touch again in most cases. I'm glad I passed that exam and never have to deal with them.

 

[txrandom]

Thanks for the insight newnameman. I think that's the right direction. I got to take a break and then work on it again.

 

[seemingly random]

Originally posted by: GodlessAstronomer

Originally posted by: AstroManLuca
Seriously, what the fuck are you guys talking about? Is this some sort of programming thing that I will never in a million years understand? Is this entire thread some joke that I'm not getting?

:laugh: It's not really programming, it's esoteric computer science stuff. It's the kind of thing you learn, pass an exam then never touch again in most cases. I'm glad I passed that exam and never have to deal with them.

I think the concepts are used in yacc...

Before he got interested in conspiracies, noam chomsky cared about this in his work in linguistics.

 

[fulltilt39]

Originally posted by: GodlessAstronomer

Originally posted by: AstroManLuca
Seriously, what the fuck are you guys talking about? Is this some sort of programming thing that I will never in a million years understand? Is this entire thread some joke that I'm not getting?

:laugh: It's not really programming, it's esoteric computer science stuff. It's the kind of thing you learn, pass an exam then never touch again in most cases. I'm glad I passed that exam and never have to deal with them.

oohhhh...like calculus!! i get it.

 

[MAKENITO]

Originally posted by: txrandom

Originally posted by: AstroManLuca
Seriously, what the fuck are you guys talking about? Is this some sort of programming thing that I will never in a million years understand? Is this entire thread some joke that I'm not getting?

Formal Language
CFG

The answer AML is yes.

 

[GodlessAstronomer]

Originally posted by: fulltilt39

Originally posted by: GodlessAstronomer

Originally posted by: AstroManLuca
Seriously, what the fuck are you guys talking about? Is this some sort of programming thing that I will never in a million years understand? Is this entire thread some joke that I'm not getting?

:laugh: It's not really programming, it's esoteric computer science stuff. It's the kind of thing you learn, pass an exam then never touch again in most cases. I'm glad I passed that exam and never have to deal with them.

oohhhh...like calculus!! i get it.

Don't make Dr Pizza come in here and tell you about how calculus saved his roast beef.

 

[FoBoT]

if only we had a homework forum

 

[Mojoed]

Originally posted by: AstroManLuca
Seriously, what the fuck are you guys talking about? Is this some sort of programming thing that I will never in a million years understand? Is this entire thread some joke that I'm not getting?

^ This, or SpaceMan hackz0r'd the OP's account.