• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Context Free Grammar

T

txrandom

Diamond Member
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.
 
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 😛
 
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
Click to expand...

Oops,

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

IJ => IIJJJ
IK => IIJJK
 
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
Click to expand...

Oops,

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

IJ => IIJJJ
IK => IIJJK
Click to expand...

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.
 
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
Click to expand...

Oops,

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

IJ => IIJJJ
IK => IIJJK
Click to expand...

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.
Click to expand...

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).
 
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?
 
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?
Click to expand...

Formal Language
CFG
Click to expand...

Well maybe this should be in programming or something then.
Click to expand...

Nah, only a few programmers even touch this stuff. This stuff was around long before computers and programming.
 
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
Click to expand...

Oops,

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

IJ => IIJJJ
IK => IIJJK
Click to expand...

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.
Click to expand...

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).
Click to expand...

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
 
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?
Click to expand...

: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.
 
Thanks for the insight newnameman. I think that's the right direction. I got to take a break and then work on it again.
 
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?
Click to expand...

: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.
Click to expand...
I think the concepts are used in yacc...

Before he got interested in conspiracies, noam chomsky cared about this in his work in linguistics.
 
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?
Click to expand...

: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.
Click to expand...

oohhhh...like calculus!! i get it.
 
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?
Click to expand...

: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.
Click to expand...

oohhhh...like calculus!! i get it.
Click to expand...

Don't make Dr Pizza come in here and tell you about how calculus saved his roast beef.
 
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?
Click to expand...

^ This, or SpaceMan hackz0r'd the OP's account.
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top