MHB Is left recursion present in this grammar with the given productions?

[mathmari]

Hey!

Does the following part of a grammar contains left recursive productions?
$$S \to aSb$$

A left recursive production is of the form $I \to IA|B$.

 

[I like Serena]

Hey!

Does the following part of a grammar contains left recursive productions?
$$S \to aSb$$

A left recursive production is of the form $I \to IA|B$.

Hey yourself! :p

From wiki:

In terms of context-free grammar, a non-terminal r is left-recursive if the left-most symbol in any of r’s productions (‘alternatives’) either immediately (direct/immediate left-recursive) or through some other non-terminal definitions (indirect/hidden left-recursive) rewrites to r again.​

Is S either directly or indirectly the left-most symbol in its production?

 

[mathmari]

Hey yourself! :p

From wiki:

In terms of context-free grammar, a non-terminal r is left-recursive if the left-most symbol in any of r’s productions (‘alternatives’) either immediately (direct/immediate left-recursive) or through some other non-terminal definitions (indirect/hidden left-recursive) rewrites to r again.​

Is S either directly or indirectly the left-most symbol in its production?

Since at the left and at the right side of $S$ is a symbol, $S$ is not the left-most symbol in its production, so the production is not left recursive, is it?

 

[I like Serena]

Since at the left and at the right side of $S$ is a symbol, $S$ is not the left-most symbol in its production, so the production is not left recursive, is it?

Yep.

 

[mathmari]

Nice!

Could you also tell me if the production $S \to aSa|bSb|c$ has a dilemma?
We have dilemma when $I \to rK$ and $I \to rL$.

The production $S \to aSa|bSb|c$ means that $S \to aSa$, $S \to bSb$, $S \to c$, is this of the form above? At the first two cases there is the same symbol $S$ at the right side of the production. Or does it have to have only the same terminal symbols to have dilemma?

 

[I like Serena]

Nice!

Could you also tell me if the production $S \to aSa|bSb|c$ has a dilemma?
We have dilemma when $I \to rK$ and $I \to rL$.

The production $S \to aSa|bSb|c$ means that $S \to aSa$, $S \to bSb$, $S \to c$, is this of the form above? At the first two cases there is the same symbol $S$ at the right side of the production. Or does it have to have only the same terminal symbols to have dilemma?

Well, I can't find "dilemma" with Google in this context.
But yeah, it would need to have the same left-most terminal symbol.

Typical reason why we would like to know, is to be able to uniquely decide, based on the next symbol on the input, which rule we should apply.
That makes for an unambiguous language with a one-token-look-ahead.
As a consequence, it's relatively easy to create a parser for it.

 

[mathmari]

Well, I can't find "dilemma" with Google in this context.
But yeah, it would need to have the same left-most terminal symbol.

Typical reason why we would like to know, is to be able to uniquely decide, based on the next symbol on the input, which rule we should apply.
That makes for an unambiguous language with a one-token-look-ahead.
As a consequence, it's relatively easy to create a parser for it.

Ok!
And something else. The part $$S \to Sa|b$$ contains left recursive production, right?
How can I eliminate it?

 

[I like Serena]

Ok!
And something else. The part $$S \to Sa|b$$ contains left recursive production, right?
How can I eliminate it?

Well, you can't usually eliminate a recursion.
But you can convert it to a right recursion, which is needed to turn a grammar into a regular grammar (that is easy to recognize by a deterministic state machine).

What kind of strings can your production rule make?
Can you rephrase it to be right recursive?

 

[mathmari]

What kind of strings can your production rule make?
Can you rephrase it to be right recursive?

This production rule creates strings of the form $baa...aa$,so can we rephrase this rule to be right recursive as followed?
$$S \to b|bS', S' \to aS'| \varnothing $$

 

[I like Serena]

This production rule creates strings of the form $baa...aa$,so can we rephrase this rule to be right recursive as followed?
$$S \to b|bS', S' \to aS'| \varnothing $$

Yep!
Note that you can limit yourself to:
$$S \to bS', S' \to aS'| \varnothing $$

 

[mathmari]

Yep!
Note that you can limit yourself to:
$$S \to bS', S' \to aS'| \varnothing $$

Nice! Thanks a lot!