Can You Convert a Context-Free Grammar to a Deterministic One?

[evinda]

Hello! (Blush)

I have a context-free grammar,that I want to convert in a deterministic one.

This is the context-free grammar:

I -> cdaX|cdbY, X-> XXX |d , Y -> I | X

That's what I have tried:



I -> cdK , K ->aX | bY
X -> dM, M -> d M |N, N-> dN | ∅
Y ->cdK| dM

Is it right? Or have I done something wrong? (Thinking)

 

[I like Serena]

Hello! (Blush)

I have a context-free grammar,that I want to convert in a deterministic one.

This is the context-free grammar:

I -> cdaX|cdbY, X-> XXX |d , Y -> I | X

That's what I have tried:



I -> cdK , K ->aX | bY
X -> dM, M -> d M |N, N-> dN | ∅
Y ->cdK| dM

Is it right? Or have I done something wrong? (Thinking)

Hi!

It is almost right. (Worried)

Is for instance [m]cdadd[/m] allowed? (Wondering)

 

[evinda]

Hi!

It is almost right. (Worried)

Is for instance [m]cdadd[/m] allowed? (Wondering)

Do you mean that it should be like that?

I -> cdK , K ->aX | bY
X -> dM, M -> d M | ∅
Y ->cdK| dM

?
(Thinking)

 

[I like Serena]

Do you mean that it should be like that?

I -> cdK , K ->aX | bY
X -> dM, M -> d M | ∅
Y ->cdK| dM

?
(Thinking)

No... my point was that the original language does not allow [m]cdadd[/m], while your languages both do. (Doh)

 

[LudusRex]

Hello there!

I can provide some feedback on your attempt to convert the context-free grammar to a deterministic one. Overall, your approach is on the right track, but there are a few things that could be improved.

First, it's important to note that a deterministic grammar should have only one production rule for each non-terminal symbol. In your conversion, you have multiple production rules for the non-terminal symbol X (dM and N). This could lead to ambiguity and make the grammar non-deterministic.

Additionally, I see that you have introduced a new non-terminal symbol K, which is not present in the original grammar. This is not necessary in a deterministic conversion and could potentially create more confusion.

In order to make your grammar more deterministic, I would suggest the following modifications:

I -> cdA | cdB | cdC
A -> dX | ∅
B -> dM | ∅
C -> dN | ∅
X -> X | ∅
M -> M | ∅
N -> N | ∅

This conversion ensures that each non-terminal symbol has only one production rule, and it eliminates the need for the extra non-terminal symbol K. I hope this helps. Keep up the good work!