# Is this rule a left recursive production?

#### mathmari

##### Well-known member
MHB Site Helper
Hey!!!

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

#### Evgeny.Makarov

##### Well-known member
MHB Math Scholar
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

##### Well-known member
MHB Site Helper
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$$

Last edited:

#### mathmari

##### Well-known member
MHB Site Helper
Or is there an other way to make the grammar deterministic?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### Well-known member
MHB Site Helper
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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

##### Well-known member
MHB Site Helper
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.