- Thread starter
- #1
- Apr 14, 2013
- 4,412
Hey!!! 
I have a question..
Is the rule $$X \to XX|a$$ a left recursive production?
I have a question..
Is the rule $$X \to XX|a$$ a left recursive production?
To make the grammar deterministic do I have to do the following changes?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$$
I have a 3 step plan!Or is there an other way to make the grammar deterministic?
A grammar is not determinitic if we have at least one of these two factors:1. What does a deterministic grammar look like?
This states when the grammar is guaranteed to be not deterministic.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?
Besides not having a dilemma nor a left recursion, what else should be satisfied so that the grammar is deterministic?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?
It is at least not obviously 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?