MHB Is this rule a left recursive production?

[mathmari]

Hey!

I have a question..
Is the rule $$X \to XX|a$$ a left recursive production?

 

[Evgeny.Makarov]

Not a specialist in this, but since $X$ generates a sentential form $XX$ with $X$ as the leftmost symbol, yes, $X$ is left-recursive. I am looking at Wikipedia, which has definitions for a left-recursive nonterminal and a left-recursive grammar, but not a left-recursive production.

 

[mathmari]

Not a specialist in this, but since $X$ generates a sentential form $XX$ with $X$ as the leftmost symbol, yes, $X$ is left-recursive. I am looking at Wikipedia, which has definitions for a left-recursive nonterminal and a left-recursive grammar, but not a left-recursive production.

To make the grammar deterministic do I have to do the following changes?
$$ X \to aT ,T\to XT|\varnothing$$

 

[mathmari]

Or is there an other way to make the grammar deterministic?

 

[I like Serena]

To make the grammar deterministic do I have to do the following changes?
$$ X \to aT ,T\to XT|\varnothing$$

Or is there an other way to make the grammar deterministic?

I have a 3 step plan! ;)

1. What does a deterministic grammar look like?
2. Can you give a regular expression that describes the language?
3. Can you write that regular expression as a deterministic grammar?

 

[mathmari]

1. What does a deterministic grammar look like?

A grammar is not determinitic if we have at least one of these two factors:
1. <<dilemma>>: $Q \to kA$ and $Q \to kB$
2. <<left recursion>>: $Q \to QY|X$

So to construct the determinitic version of the grammar we do the following:
For 1. $Q \to kX$ and $X \to A|B$
For 2. $Q \to X|XT, T \to YT| \varnothing$So, for my case, is $ X \to aT, T \to XT| \varnothing$ correct?

 

[I like Serena]

A grammar is not determinitic if we have at least one of these two factors:
1. <<dilemma>>: $Q \to kA$ and $Q \to kB$
2. <<left recursion>>: $Q \to QY|X$

This states when the grammar is guaranteed to be not deterministic.
The negation does not necessarily make it deterministic.

Suppose for instance we have a rule like $Q \to aQb$.
That is not a dilemma, nor a left recursion.
Does that make it deterministic?

Perhaps you can find a form that is guaranteed to be deterministic?

So to construct the determinitic version of the grammar we do the following:
For 1. $Q \to kX$ and $X \to A|B$
For 2. $Q \to X|XT, T \to YT| \varnothing$

So, for my case, is $ X \to aT, T \to XT| \varnothing$ correct?

 

[mathmari]

This states when the grammar is guaranteed to be not deterministic.
The negation does not necessarily make it deterministic.

Suppose for instance we have a rule like $Q \to aQb$.
That is not a dilemma, nor a left recursion.
Does that make it deterministic?

Perhaps you can find a form that is guaranteed to be deterministic?

Besides not having a dilemma nor a left recursion, what else should be satisfied so that the grammar is deterministic?

Does the part of the grammar $X \to aT, T \to XT| \varnothing$, have something that makes the grammar non deterministic?

 

[I like Serena]

Besides not having a dilemma nor a left recursion, what else should be satisfied so that the grammar is deterministic?

Does the part of the grammar $X \to aT, T \to XT| \varnothing$, have something that makes the grammar non deterministic?

It is at least not obviously deterministic.

As it is we can substitute the first rule in the second and get:
$$T \to aTT$$
Now without knowing what else $T$ might map to, this does not look good.
It suggests that we need to keep track of the first $T$ to be able to verify if the second $T$ "fits", which is what a deterministic language will not allow.