Welcome to our community

Be a part of something great, join today!

Is this rule a left recursive production?

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,047
Hey!!! :eek:

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

Evgeny.Makarov

Well-known member
MHB Math Scholar
Jan 30, 2012
2,492
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
Apr 14, 2013
4,047
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
Apr 14, 2013
4,047
Or is there an other way to make the grammar deterministic?
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,774
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
Apr 14, 2013
4,047
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
Mar 5, 2012
8,774
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
Apr 14, 2013
4,047
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
Mar 5, 2012
8,774
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.