- 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?

- Thread starter mathmari
- Start date

- 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?

- Jan 30, 2012

- 2,516

- Thread starter
- #3

- Apr 14, 2013

- 4,412

To make the grammar deterministic do I have to do the following changes?

$$ X \to aT ,T\to XT|\varnothing$$

Last edited:

- Thread starter
- #4

- Apr 14, 2013

- 4,412

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

- Admin
- #5

- Mar 5, 2012

- 9,135

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?

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?

- Thread starter
- #6

- Apr 14, 2013

- 4,412

A grammar is not determinitic if we have at least one of these two factors:1. What does a deterministic grammar look like?

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?

- Admin
- #7

- Mar 5, 2012

- 9,135

This states when the grammar is guaranteed to beA 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$

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?

- Thread starter
- #8

- Apr 14, 2013

- 4,412

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 benotdeterministic.

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?

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

- Admin
- #9

- Mar 5, 2012

- 9,135

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?

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.